hdu 4932 /bestcoder B题 #4 /思维题
2024-09-07 04:51:05
题意：给一个数列（整数），用一些不相交的区间去覆盖（只能是用端点去覆盖，端点可以交）。而且区间出度相等。求最大区间长度。
开始一下就敲了，枚举每个区间长度，判断合法，更新最大。但是后来一看小数，感觉不行，改为二分，后来还是挂了。。。
赛后才知道，二分的时候，答案必需要满足单调性啊，这里小的数据不行，大的数据可以行！如 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;
}
最新文章
- 最小生成树——kruskal算法
- 用python实现，冒泡排序演示
- JavaScript的一些知识碎片(2)-反射-全局变量-回调
- Spring3系列11- Spring AOP——自动创建Proxy
- Android调用蓝牙打印机
- JQuery文件上传插件uploadify在MVC中Session丢失的解决方案
- 程序破解之 API HOOK技术 z
- JVM的参数设置与OutOfMemoryError异常关系
- POJ 3107-Godfather（树形dp）
- sublime中使用markdown
- 04_Nginx命令行参数，控制信号，Nginx启动、停止、重启命令
- Debian社区群龙无首
- dattime和timestamp的异同
- Python中如何设置输出文字的颜色
- IT行业­——Linux
- bzoj 3325 密码 - Manacher
- React native 之android的图标和启动图片
- Ubuntu 14.04 安装 Xilinx ISE 14.7 全过程（转）
- JFace TableViewer性能改善 -- 使用VirtualTable
- plt绘制 2维、3维散点图