首页 > 代码库 > hdu 4932 /bestcoder B题 #4 /思维题
hdu 4932 /bestcoder B题 #4 /思维题
题意:给一个数列(整数),用一些不相交的区间去覆盖(只能是用端点去覆盖,端点可以交)。而且区间出度相等。求最大区间长度。
开始一下就敲了,枚举每个区间长度,判断合法,更新最大。但是后来一看小数,感觉不行,改为二分,后来还是挂了。。。
赛后才知道,二分的时候,答案必需要满足单调性啊,这里小的数据不行,大的数据可以行!如 0 1 5 6 10, 3不行,4行。
后来才知道,枚举时,每个差值的一半也是可以的:仔细想想很容易证明。(水,坑)
#include<iostream> #include<vector> #include<cstdio> #include<algorithm> using namespace std; vector<int>v; int n; bool ok(double tmax) { int fl=-1; for(int j=1;j<n-1;j++) { if(fl==-1) //之前的放在前 { if(v[j]-tmax<v[j-1]) //放前面不行,放后面: { if(v[j]+tmax<=v[j+1]) //放后面 { fl=1; if(v[j]+tmax==v[j+1]) //下一个免了 { j++; fl=-1; } } else //否则不行 return 0; } else //放前面 fl=-1; } else //之前的在后面, { if(v[j]-tmax<v[j-1]+tmax) //放前面放不来 { if(v[j]+tmax<=v[j+1]) { fl=1; if(v[j]+tmax==v[j+1]) { j++; fl=-1; } } else { return 0; } } else { fl=-1; } } } return 1; } vector<double>dis; int main() { int T; cin>>T; while(T--) { cin>>n; int tx=0; v.clear(); dis.clear(); for(int i=0;i<n;i++) { cin>>tx; v.push_back(tx); } sort(v.begin(),v.end()); for(int i=0;i<n-1;i++) { double d=v[i+1]-v[i]; dis.push_back(d); dis.push_back(d/2.0); } sort(dis.begin(),dis.end()); for(int i=dis.size()-1;i>=0;i--) { if(ok(dis[i])) { printf("%.3lf\n",dis[i]); break; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。