GLASNICI 解题报告
题目描述
有N个人在一直线上,第i个人的位置为Di,满足Di≤Di+1。最初只有第1个人(在最左边)知道消息。 在任意时刻,每个人可以以每秒1单位的速度向左或向右移动,或者停在原地。如果两个人的距离不超过K,那么就可以进行消息传递。求所有人都知道消息最少需要多少时间。
输入
第一行一个正实数K,表示最大的消息传递距离;
第二行一个整数N,表示有N个人; 以下N行,每行一个正实数,表示每个人的位置,第i行表示第i个人的位置Di。
输出
输出共一行一个实数,即所有人知道消息的最短时间。(结果保留三位小数点,四舍五入)
感谢@gzh01 提供的翻译
从gugu上扒下来的题面↑↑↑
思路
对于30%的数据
暴力一下,跑一下。 具体本人不会(qwq) 据说好像就是把标算的二分该成循环。。。
对于100%的数据
二分+贪心 可以二分答案啦。。。 那么check函数就使用贪心的思想。 因为D数组是单调性的,所以可以直接扫一遍。 其实也就是判断一下加上k后能不能到达下一个人。 也就是这样:
bool check(double x){
double L=d[1]+x;
for(int i=2;i<=n;i++){
if(L+k<d[i]-x) return 0;//到不了,返回false
L+=k;//加上k的单位距离
if(d[i]+x<L) L=d[i]+x;//超过了当前枚举的i的位置,直接修改成当前位置。
}
return 1;//返回true
}
L表示当前最大能到哪里。
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#define ll long long
#define eps 1e-10 //精度啦啦啦啦啦
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void write(int zx){
if(zx<0) putchar('-'),zx=-zx;
if(zx<10) putchar(zx+'0');
else{
write(zx/10);
putchar(zx%10+'0');
}
}
int n;
double k,l=0,r=1e9,ans,d[100010];
bool check(double x){
double L=d[1]+x;
for(int i=2;i<=n;i++){
if(L+k<d[i]-x) return 0;
L+=k;
if(d[i]+x<L) L=d[i]+x;
}
return 1;
}//check上面解释过,不再解释了。
int main(){
cin>>k;n=read();
for(int i=1;i<=n;i++) cin>>d[i];
while(r-l>=eps){
double mid=(l+r)/2.0;
if(check(mid)) r=mid,ans=r;
else l=mid;
}//浮点数二分
printf("%.3lf
",ans);
}