CF823div2B

cf823div2B

题目链接

题目大意

多组测试数据，有\(n\)个点在数轴上，他们想要集会，每个点到目标点\(y\)的时间为$$t_i+|x_i-y|$$

试求所有点到\(y\)中最长时间的最小值。

思路

一共有三种解法。

一，枚举时间二分，对于每个时间，去判断每个\(x_i\)所能到达的地方。会得到一个一个区间。当最小的区间右端点和最大的区间左端点恰有交集的点就是我们的目标。

二，三分地点，这个只是大概思路，没有细想，但是有题解是这样做的

三，转化。对于每个\(x_i\)可以分成两个点\(x_i-ti,xi+ti\)。这样整个区间会出现\(2n\)个点。可以证明，答案\(y\)一定位于这些点构成的区间之中。先考虑一般情况，\(y=(x_{min}^`+x_{max}^`)/2\)

这个结论对于\(y\)位于扩展到两个\(x_i\)中间是很容易成立的。再考虑特殊情况。假设\(x_{max}^`\)对应的\(x_i\)在\(y\)的左边，那么可以得到最小的那个 \(x_{min}^、\) 一定也是\(x_i\)扩展的。换句话说，\(y\)点一定是和\(x_i\)重合，同上面公式相同。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define rep(i,l,n) for(int i=(l);i<=(n);++i)
#define ll long long
#define N 100005
using namespace std;
double eps=1e-9;
int t,n;
int x[N],a[N];
double pd(int x)
{
    double ans=0;
    rep(i,1,n)
    {
        ans=max(ans,fabs(x-i)+a[i]);
    }
    return ans;
}
void solve()
{
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",&a[i]);
    rep(i,1,n)scanf("%d",&x[i]);
    vector<int> g;
    rep(i,1,n)
    {
        g.push_back(a[i]-x[i]);
        g.push_back(a[i]+x[i]);
    }
    int mn=g.front(),mx=g.front();
    for(auto xi:g)
    {
        mn=min(xi,mn);
        mx=max(xi,mx);
    }
    printf("%d",(mx+mn)/2);
    if((mn+mx)&1)printf(".5");
    cout<<endl;
    return ;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
	system("pause");
    return 0;
}	

原文地址：http://www.cnblogs.com/Vertrag/p/16786559.html