蓝桥杯之二分-爱代码爱编程
但是左端点的更新也要自己找规律，扫地机器人是根据当前遍历到的机器人的位置和左端点L的位置的前后不同更新L，区间移位是根据L和当前遍历到的区间最大能移到L的左边还是右边，以及区间右端点来看的。
区间移位
-
举例区间a【1 ~ 10】，b【2 ~ 4】 或 a1【1000,2000】，b1【1200,1300】
对于左端点极小右端点极大的长度很大的区间a，应该合理加以利用，移动到右侧最近的位置，防止左端点更大右端点更小的区间b，因为不合理的移动（如果按左端点排序，b区间后于a区间移动，b区间移动某种程度上需要跨过a区间的长度距离，到达a的右端点才能找到未被覆盖的点再进行拼接）而导致的移动位移增大，不管用哪种贪心方法永远是要找到最左的未被覆盖的点进行拼接，
按右端点排序，避免因区间程度造成的位移增多（长度短的区间需要徒劳移出长度长的区间再去补空白区间） -
分析样例可以知道，答案可能存在0.5,1.5,2.5等。那么我们将所有数值扩大两倍，最后再除2就可以了。
1、需要多次遍历区间
3、二分判断是否可行，每次判断都需要对edge和vis数组初始化
4、vis数组来防止区间重复利用，如果用vector数组也可以tmp.erase(tmp.begin()+i) （注意括号里面是迭代器）
2、每找到一个可行区间，结束循环？？？突然发现用vis数组标记的方式不需要每找到一个可行区间就break，但是用vector数组erase的方式，如果不break就只能过30%，好了，都是erase之后指针错乱，代码解释
每删除一个元素就i-- 让指针回溯一个位置，因为此时被删除元素的后一个元素 对应的下标就是此时的i
vector<int> v;
v.clear();
v.push_back(0);
v.push_back(1);v.push_back(2);
v.push_back(3);v.push_back(4);
v.push_back(5);v.push_back(6);
for(int i=0;i<v.size();i++){
cout<<v[i]<" ";
if(v[i]&1){
v.erase(v.begin()+i);
i--;
}
#include<bits/stdc++.h>
#include<algorithm>
#include<iomanip>
using namespace std;
const int N=1e4+5;
typedef struct node{
int l,r;
bool operator<(const node & p)const{
return r<p.r;
}
}node;
int n,x,y;
node a[N];
int vis[N];
bool adequate(int x){//位移差最大的那个区间的位移量为x
int edge=0;
memset(vis,0,sizeof(vis));
while(true){
bool flag=false;
for(int i=0;i<n;i++){
int sl=a[i].l,sr=a[i].r;
if(!vis[i]&&sl-x<=edge&&sr+x>=edge){//移动区间可能 覆盖第一个未被覆盖的点
int len=sr-sl;
// 覆盖之后，edge(被覆盖的右端点)能延伸到哪儿呢 edge+len or sr+x
// 不一定要移动x这么远，如果sl+x>=edge(移动之后 sl会超出edge)
// 注意这里有两种情况，sl>x 或者sl<x，前者向左移，后者向右移动
if(sl+x>=edge)edge+=len;
else edge=sr+x;
vis[i]=1;
flag=true;
if(edge>=20000)return true;
break;
}
}
if(!flag&&edge<20000)return false;
}
//if(edge>=20000)return true;或者这一句写在这里
}
signed main(){//8:32 位移差最大的那个区间的位移量最小
cin>>n;
for(int i=0;i<n;i++){
cin>>x>>y;
a[i].l=x*2;
a[i].r=y*2;
}
sort(a,a+n);
int l=0,r=1e4*2;
while(l<r){
int mid=l+r>>1;
if(adequate(mid))r=mid;
else l=mid+1;
}
cout<<l/2.0;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, a, b;
struct node
{
int a, b;
};
vector<node> q;
bool cmp(node x, node y)
{
return x.b < y.b;
}
bool check(int m) //最大移动距离m，判断是否能覆盖整个区间;
{
vector<node> tmp(q); //建立一个q的复制tmp;
int k = 0; //最大能覆盖的区间右端点;
while(true)
{
bool flag = false;
for(int i = 0; i < tmp.size(); i++)
{
node now = tmp[i];
int ta = now.a;
int tb = now.b;
if(ta-m <= k && tb+m >= k) //k在区间[ta-x, tb+x]内，不在则m太小;
{
flag = true;
int len = tb - ta; //当前这个区间的长度;
if(ta+m >= k)
k = k + len; //k最大能多覆盖到k+len的范围;
//ta+x>=k，那么只需要让区间的左端点移动到k处，右端点此时在k+len处;
else
k = tb + m; //ta+x<k，k最大能多覆盖到该区间的右端点，再多走m的长度;
tmp.erase(tmp.begin()+i); //将选择的区间去掉，避免重复判断;
// break; i--使得指针i不受erase的影响继续指向下一些个元素
i--;
if(k >= 20000)return true;
}
}
if(k >= 20000 || !flag) break;
//如果找不到可以覆盖的区间，或者k已经达到20000了，就可以结束检验了;
}
return false;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a >> b;
a *= 2; //答案存在0.5，可以将所有东西扩大两倍，最后再除2就可以了;
b *= 2;
q.push_back({a, b});
}
sort(q.begin(), q.end(), cmp); //按右端点从大到小排序;
int l = 0, r = 20000; //因为扩大了2倍，枚举答案范围也大了2倍;
while(l < r) //二分答案：枚举最大移动的距离，使最大移动距离最小;
{
int mid = (l+r)/2;
if(check(mid))
r = mid ;
else
l = mid + 1;
}
double ans = (l) / 2.0;
cout << ans << endl;
return 0;
}
扫地机器人
解题思路：不用遍历所有机器人的运动轨迹，只需要求出单个机器人花的最大时间
即可完成本题，利用二分查找查找最大时间
步骤：
1.利用二分查找每次分两个区域
2.定义检查函数检查是否扫完
3.在函数体内遍历每个机器人一次性扫多少个地，这个地我们用x表示，求出最小x即可
在定义一个s代表扫了多少个地，遍历完在判断s是否>=n即可，
由于每个机器人扫的地都一样，所以最后的结果一定会>=n
4.那个最小的x就是我们的最终结果
假设某个机器人需要清扫 a,b,c,d 四个格子，因为这个机器人清扫完还需要回到最初始的位置，所以无论这个机器人初始位置在什么地方，
其清扫路径的本质都是重复两次 a 到 b，b 到 c，c 到 d 的过程，花费时间为 6，由此，假设某个机器人清扫的格子范围为 l,
那么这个机器人花费的时间为
(
l
−
1
)
×
∗
2
(l-1)\times*2
(l−1)×∗2。所以只需要对机器人清扫的范围（l）进行二分即可，最后的答案为
t
=
(
l
−
1
)
×
∗
2
t=(l-1)\times*2
t=(l−1)×∗2。
显然当每个机器人清扫的范围大小相同时，花费时间最小。
可以对清扫范围进行二分，然后验证其答案的正确性即可，判断条件是清扫范围可以使得每个格子都能够扫到
可以明显的知道，最左边的格子由左边第一台机器人清扫，花费时间是最少的，在此可以采用贪心的思想，
让每台机器人都要优先清扫其左边还未扫的到格子，然后再往右扫，在二分得到的范围下往右扫得越多越好，
这样可以减少右边下一个机器人需要往左扫的范围，增加其往右扫的范围，以此类推，可减少清扫时间。
综上，本题采用二分加贪心的思想解答。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k;
int a[N];
bool adequate(int x){//假设每个机器人能扫过x个点
int edge=0;
for(int i=0;i<k;i++){
if(a[i]-x>edge)return false;
if(a[i]<edge)edge=a[i]+x-1;// 2 3 4 假设a[i]为2，x=3,则可以扫到2 3 4
else edge=a[i]+x-1-(a[i]-edge-1);//机器人a[i]往左走 走到扫到edge，这样一来
// 十分注意x是能扫过的点，暂时不要考虑路程，原先edge在a[i]左边，a[i]左右扫x个点
// 于是edge`=edge+x
}
return edge>=n;
}
signed main(){
cin>>n>>k;
for(int i=0;i<k;i++){
cin>>a[i];
}
sort(a,a+k);
int l=0,r=n;//机器人打扫的范围，路程为 (范围-1)*2
// 注意了这里的打扫范围指的是机器人能经过的所有点，
// n个方格区域假设只有1个机器人，那么该机器人的打扫范围就是n，实际上路程为(n-1)*2
while(l<r){
int mid=l+r>>1;
if(adequate(mid)){
r=mid;
}
else l=mid+1;
}
cout<<(l-1)*2;
return 0;
}