题目链接
https://codeforces.com/contest/1730/problem/B
题意简述
\(x\) 轴上有 \(n\) 个人,他们的位置分别是 \(x_i\) ,现在他们想要聚会,需要找一个位置(可以为小数),使得他们走到一起的总时间最短 , 每个人在出发前需要 \(t_i\) 的时间穿好衣服 , 然后才能出发.他们走到 \(x_0\) 所需要的时间就是 \(t_i+\)\(|x_i-x_0|\),请你帮助他们找到在哪个位置相遇能使得总时间最短.
样例
点击查看样例
分析
比赛时完全没有头绪.补题之前复盘了一下这题突然想到可以二分做,但是具体想不出来怎么实现,遂看题解.
这道题要么以时间二分,要么以位置二分,简单推理可以发现位置没有二分性.
以时间二分.就看所用当前这个时间能否让所有人都达到某一点.
如果当前要求时间为 \(T\) ,那么在 \(x_i\) 的点所能走到的位置就是 \([\ a[i]-(T-t[i])\ ,\ a[i]+(T-t[i])\ ]\).
对于所有人所能走到的位置取交集即可,如果交集为空( \(r-l\) 小于\(0\))
题外话就是EPS取到\(1e^{-8}\)时 $ TLE$ 了,EPS取到 \(1e^{-7}\) \(AC\)
代码
点击查看代码
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const double EPS =1e-7;
int a[N];
int t[N];
int n;
struct section
{
double l,r;
};
section merge(section a,section b)//merge:合并
{
return {max(a.l,b.l),min(a.r,b.r)};
}
double res;
double temp_l;
int print=0;
int check(double T)
{
section all={INT32_MIN,INT32_MAX};
for(int i=1;i<=n;i++)
{
double rest_t=T-t[i];
if(rest_t<0)return false;
section p={a[i]-rest_t,a[i]+rest_t};
all=merge(all,p);
}
double l=all.l,r=all.r;
if(r-l>=EPS)
{
temp_l=l;
if(print)
printf("可行区间%lf %lf\n",l,r);
}
return r-l>=EPS;
}
int main()
{
//freopen("uva.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
double l=INT32_MAX,r=0x3f3f3f3f;
for(int j=1;j<=n;j++)
{
scanf("%d",&t[j]);
l=min(l,(double)t[j]);
}
while(r-l>EPS)
{
double mid=(l+r)/2;
if(print)
cout<<l<<" "<<r<<" "<<mid<<endl;
if(check(mid))
{
r=mid;
res=temp_l;
}else l=mid;
}
printf("%lf\n",res);
}
return 0;
}