题目链接

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;
}

:::