二分+贪心， 二分和贪心总是同时出现嘛 ， 二分倒是简单，贪心总是很难证明也很难想到，
参考一下这两个博客
蓝桥杯历年真题——区间位移——JAVA 详解_蓝桥杯 区间位移-CSDN博客
蓝桥杯国赛第八届c++ A组 区间移位_数轴上有n个闭区间d1,…,dn。其中区间di用一对整数[ai, bi]来描述,满足ai < bi。-CSDN博客
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std ; const int N = 1e4 + 10 ; struct node{ int a,b ; node(int aa, int bb){ a = aa, b = bb ; } }; bool cmp(node q,node w){ return q.b < w.b ; } int n ; vector<node> q ; bool check(int mid){//先找出一个mid值 int pos = 0 ; vector<node> temp(q) ;//复制原来数组，因为我们后边会对数组中的某些个点进行清楚，为了不影响下一次二分，我们用这个复制数组来操作 while(1){ bool flag = false ;//如果循环结束后还是false 说明区间有了不能补上的空点，如果还没有到达最后的点20000直接返回0 ； for(int i = 0 ; i < temp.size() ; i++ ){//从头到尾遍历每一个区间，如果又符合条件的就把这个区间放上去，对pos值进行修改 int na = temp[i].a , nb = temp[i].b ; int len = nb - na ;//当前区间左端，右端，长度 if(na - mid <= pos && nb + mid >= pos){//当前pos 在区间内，或者在移动后区间内，这样的区间符合条件 flag = 1 ;//找到一个符合条件的区间了，进行下一次循环 //两种情况的pos的值的更新 if(na + mid >= pos) pos += len ; // 1.最左端移动小于等于mid就可以到达pos，那pos直接加上区间长度len else pos = nb + mid ;//2.最左端移动了mid了，但是还不到不了pos，就只能让去掉重复的那一块了， temp.erase(temp.begin()+i) ;//避免区间重复判断 break; //找到一个符合的了，重新开始从头找 } } if(pos>=20000 || !flag) break ; } return pos >= 20000 ; } int main(){ cin >> n ; for(int i = 0 ; i < n ;i ++){ int a, b ; cin >> a >> b ; a*=2,b*=2 ; q.push_back(node(a,b)) ; } sort(q.begin(),q.end(),cmp) ; // 这是vector 的排序方法，一定要记住 int l = 0 , r = N ; while(l<r){//二分 int mid = l + r >> 1 ; if(check(mid)) r = mid ; else l = mid + 1 ; } cout << ((double)r ) / 2 << endl ;//因为刚开是把数组都扩展了一倍，所以数组先都乘2 }
