题目
代码
#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 的值。