题解：P11677 [USACO25JAN] Shock Wave P

wmrqwq · 2026-03-04 21:09:43 · 题解

题目链接

P11677 [USACO25JAN] Shock Wave P

解题思路

下文中设下标从 1 开始。

:::info[结论一] 对于操作的最小值的方案，一定只有至多一个操作点 x 满足 2 \le x \le n - 1，其余操作点都满足 x = 1 或 x = n。 :::

:::info[结论一证明] 考虑两个操作点 u,v 满足 2 \le u \le v \le n - 1，则把这两个操作点由 u,v 修改为 u-1,v+1 一定不劣。

一直操作直到不能操作时中间至多只会剩下一个点。 :::

先不管中间的这个点，考虑求出只对 1,n 这两个点进行操作的最小次数，记最小次数为 s，则答案 ans \in [s-1,s]。

思考怎么求出这个最小次数，考虑二分答案 mid 表示操作 1,n 的次数总和。设 1,n 这两个点的操作次数分别为 x,y。

那么我们扫一遍每个位置，可以求出 x,y 的下界。

那么这样我们就容易求出 s 的值，接下来只需要 check 答案是否可能为 s - 1，感性理解一下，发现中间的操作点 pos 一定由 1,n 这两个操作点替换而来，所以我们可以顺便一起 check 这种情况，具体的：

• 若 x + y = mid，直接 check 即可。
• 若 x + y > mid，则无解。
• 若 x + y < mid，先将 x \gets mid - y - 1，那么此时还会有多余的一次操作可以放任意位置操作，容易发现由于有一些 a_i > 0，因此最后一次操作是不能放到某一些位置的，将对于每一个 a_i 的不约束的点求个交集即可 check 合法性。

时间复杂度 O(n \log V)，其中 V 为答案值域。

:::info[参考代码]

ll n;
ll a[1000010],b[1000010];
ll pre[1000010];
bool chk(__int128 Mid)
{
    forl(i,1,n)
    {
        if(a[i]-min(i-1,n-i)*(Mid-1)<0)
            b[i]=MLM;
        else
            b[i]=a[i]-min(i-1,n-i)*(Mid-1);
    }
    ll L=0,R=0,nw=n-1;
    forl(i,1,n/2)
        Max(R,(b[i]-(n-i)+nw-1)/nw),
        nw-=2;
    nw=n-1;    
    forr(i,n,(n+1)/2+1)
        Max(L,(b[i]-(i-1)+nw-1)/nw),
        nw-=2;
    if(L+R>Mid)
        return 0;
    if(L+R<Mid)
        L=Mid-R-1;
    ll maxn=0;
    forl(i,1,n)
        b[i]=a[i]-(i-1)*L-(n-i)*R,
        Max(maxn,b[i]);
    if(L+R==Mid)
        return maxn==0;
    forl(i,0,n+1)
        pre[i]=0;
    forl(i,1,n)
    {
        pre[1]++;
        if(b[i]>0)
            pre[max(0ll,i-b[i]+1)]--,
            pre[min(n+1,i+b[i])]++;
    }
    forl(i,1,n)
        pre[i]+=pre[i-1];
    forl(i,1,n)
        if(pre[i]==n)
            return 1;
    return 0;
}
void solve()
{
    cin>>n;
    forl(i,1,n)
        cin>>a[i];
    ll L=0,R=2e18/(n-1)+2;
    while(L<R)
    {
        ll Mid=(L+R)/2;
        if(chk(Mid))
            R=Mid;
        else
            L=Mid+1;
    }
    cout<<L<<endl;
}

:::