题解 P6397 【[COI2008] GLASNICI】

朝夕 · 2020-05-23 23:21:32 · 题解

解题思路

二分答案+贪心。

二分答案出最终的时间x，然后用贪心策略判断该时间是否可行。

若i号信使向右走，i+1号信使向左走，在x秒后仍旧不曾把距离缩短到k内，则该时间不可行。

若在x秒后能够缩短距离到k内，则为了更快地传递信息给i+2号信使，我们先使i号信使和i+1号信使同时向右走一段时间（此时相对距离不变），然后i+1号信使停下，让i号信使走完x秒时恰好与i+1号信使距离k。

此时i+1号信使所处的位置，就是他所能达到的极限最右位置。

接下来再考虑i+2号信使向左靠拢可不可行，若不可行，则该时间依旧不可行；若可行的话，则使i+2号信使同样先尽力往右走一段时间，走到距离i+1号信使极限最右距离相差k的位置，以使得更快接近i+3号信使。

若时间不够走不到距离为k，那走多少算多少。

以此类推。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
double d[100005];
double k;
int n;
bool check(double x)//x是最终花费的时间
{
    double maxx=d[1]+x;//1号信使极限最右位置位置
    for(int i=2;i<=n;i++)
    {
        if(d[i]-x-maxx>k) return 0;//若i号信使向左靠拢都不行，辣是真的不行
        maxx+=k;//若可以则使i号信使走到距离i-1号信使k的位置
        if(d[i]+x<maxx) maxx=d[i]+x;
        //如果用尽时间都走不到，那走多少算多少
    }
    return 1;
}
int main()
{
    scanf("%lf%d",&k,&n);
    for(int i=1;i<=n;i++) scanf("%lf",&d[i]);
    double l=0,r=d[n],ans=0;
    while(r-l>=0.000001)
    {
        double mid=(l+r)/2.0;
        if(check(mid)) ans=mid,r=mid;
        else l=mid;
    }//二分答案
    printf("%.3lf\n",ans);
    return 0;
}