题解 P3124 【[USACO15OPEN]被困在haybales】

· · 题解

写完金组再来写银组。

两题的尿性都差不多，依然是暴力能够解决的问题。 问题要求我们加固其中一个草堆以避免Bessie逃出草堆。并且当连续跑动的距离大于该草堆的大小就能打破该草堆。那么需要加固该草堆的size就等于跑动的距离减去该草堆的大小。那么我们思考某一个草堆能够被撞击的最大加速值是在不打破该草堆的前提下让Bessie随意倒腾能够开辟出的最大空间。

如果枚举左端点，那么撞击该草堆的最大加速值是Bessie向右跑能够到达的最右草堆位置减去当前草堆位置。反之亦然。

注意在枚举完上一个端点后不需要把另一边的位置极值重置为距Bessie原本最近的那个点，因为如果Bessie在不打破上一个草堆的情况下能够到达那个点，那么打破之后也一定能。

然后是其他需要注意的地方，例如什么时候输出0什么时候输出-1。输出0是指枚举完了左端点或右端点，但是另一边的位置极值始终不能到达0和n+1的情况。会导致ans的值被更新成负数，输出时用max调整一下就行。输出-1只当Bessie向任意一边跑，但是甚至不用撞破另一边的草堆的时候就能逃离的时候输出。这时ans的值不会被更新。

Solution

#include<bits/stdc++.h>
using namespace std;
long long n,b,ans=5201314314314,st=1;//这里最大值不能开的小于10^9，之前开5201314把我从前天！卡到！今天！
struct grass {
    long long s,p;/草堆的大小与位置
} gra[100005];
bool cmp(grass a,grass b) {
    return a.p<b.p;
}
int main() {
    cin>>n>>b;
    for(int i=1; i<=n; i++) 
        cin>>gra[i].s>>gra[i].p;
    sort(gra+1,gra+n+1,cmp);
    for(;st<=n;st++)
        if(gra[st+1].p>b)
            break;//之前用二分查找莫名其妙的挂了，至今未解
    int l=st,r=st+1;
    for(; l>=1; l--) {
        while(r<=n&&gra[r].p-gra[l].p>gra[r].s)//在能够向右倒腾的时候就一定要倒腾换取可能的最大的加速值
            r++;
        if(r>n)
            break;
        ans=min(ans,gra[r].p-gra[l].p-gra[l].s);//在该点至少要加固的值和ans取min
    }
    l=st;
    r=st+1;
    for(; r<=n; r++) {
        while(l>=1&&gra[r].p-gra[l].p>gra[l].s)//同上
            l--;
        if(l<1)
            break;
        ans=min(ans,gra[r].p-gra[l].p-gra[r].s);//同上
    }
    if(ans==5201314314314)
        cout<<-1;//有点绕，如果左边和右边都无论加没加固都无法阻止Bessie逃出去，那么输出-1。
    else cout<<max(ans,1ll*0);
}

I'm Schwarzkopf Henkal.