蓝桥杯 区间移位--二分、枚举

题目

代码

#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; 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);//复制一个vector q     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;             //k应该在【ta-m , tb+m】 里才能保持连接的10000长度             //下面讨论的是如果在             if(ta-m <= k && tb+m >= k){ // 如果当前区间的移动后能与 k 连接，则更新 k 的值。                 flag=true;                 int len=tb-ta;//当前区间的长度                                 if(ta+m >= k){                     k=k+len;//更新k，k可以到更远                 }                 else{                     k=tb+m;                 }                 tmp.erase(tmp.begin()+i);                 break;             }         }         if(k >= 20000 || !flag)//如果没有区间符合             break;     }      return k >= 20000;//当前假设长度m符合最终条件，可以考虑调小 } int main(){     int n;     cin>>n;     for(int i=0;i<n;i++){         int aa,bb;         cin>>aa>>bb;         //因为最后答案可能存在0.5，所以扩大两倍         //最后再除以2         aa = aa*2;         bb = bb*2;         q.push_back({aa,bb});     }     //对vector排序     sort(q.begin(),q.end(),cmp);     int l=0,r=20000;//区间     while(l<=r){         int mid=(l+r)/2;         if(check(mid)){//如果能满足最终条件，说明该mid偏大，答案在左半段，         //找最小的左端点             r=mid-1;         }         else l=mid+1;     }     //最后l=r   //cout<<l<<' '<<r<<endl;     double ans=l/2.0;//最后有0.5     cout<<ans<<endl;     return 0;     }

运行评判结果

总结：

每个区间的两个端点分别为 a 和 b，要求找到一个最小的移动距离 m，使得所有区间通过向左或向右移动不超过 m 的距离后能够连续覆盖 [0, 10000] 这个区间。由于答案可能包含 0.5，所以将输入的区间扩大了两倍来处理，最终结果再除以2。使用二分查找来确定最小的移动距离 m。首先定义搜索的上下界，然后不断缩小范围直到找到满足条件的最小 m 值。使用变量 k 来追踪当前已覆盖的最右端点。如果当前区间的移动后能与 k 连接，则更新 k 的值。