题解：CF2055D Scarecrow

Neil_Qian · 2025-01-14 19:04:08 · 题解

CF2055D Scarecrow 题解

首先乌鸦移动分为两种：随着一个稻草人向右移动，与一个稻草人相遇突然坐标 +k。

第一步一定是坐标最小的稻草人来到 0，乌鸦移动到 k。记现在乌鸦的坐标为 now，时间为 tim，接下来有几种情况：

• 如果 a_i\le now，那么 a_i 一定会向右移动但不会超过 now，超过显然是无意义的。

• 否则，如果 a_i-tim\le now，那么乌鸦同样会被赶到 now+k，a_i 在更右边没有意义。

• 否则，a_i 是剩下稻草人中坐标最小的，只能等待稻草人与其相遇，然后 now+k。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;using ll=long long;
const int N=4e5+2;ll T,n,k,l,a[N],now,tim;
int main(){
    // freopen(".in","r",stdin),freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>T;
    while(T--){
        cin>>n>>k>>l,k*=2,l*=2,now=tim=0;
        for(int i=1;i<=n;i++)cin>>a[i],a[i]*=2;
        if(a[1]!=0)tim+=a[1];
        now=k;
        for(int i=2;i<=n;i++){
            if(a[i]<=now){
                a[i]=min(a[i]+tim,now);
                if(now-a[i]<=k)now=a[i]+k;
                continue;
            }
            if(a[i]-now<=tim)now+=k;
            else{
                ll dis=a[i]-now-tim;tim+=dis/2,now+=dis/2,now+=k;
            }
        }
        if(now<l)tim+=l-now;
        cout<<tim<<"\n";
    }
    return 0;
}