题解：CF2081B Balancing

nauyng · 2026-03-04 19:27:13 · 题解

首先把极长递增段拉出来是显然的，然后考虑设 a_i>a_{i+1} 的 i 为不好点，假设有 c 个不好点，则有 c+1 个极长段。考虑每次操作最多只能消掉操作区间两端的不好点，所以答案的下界是 \lceil \frac c 2 \rceil。

然后考虑往这个下界构造方案，对于第 2 和第 3 个极长段， 把第 2 个极长段上移，第 3 个极长段下移，这样就还原了前 2 个极长段，且第 3 个和第 4 个合并成了一个极长段，然后把第 3 个极长段和第 4 个极长段一起上移，第 5 个极长段下移，这样就还原了前 4 个极长段，第 5 个和第 6 个段合并成一个段。然后以此类推。

如果有奇数个极长段，那么答案可以取到下界。如果有偶数个极长段，那么最后一步只会把一个最长段上移，那么答案就比下界多 1。

考虑用另一种操作优化，观察第 3 个样例 -2 -5 5 2，答案是 1，只需要把 [-5,5] 改成 [0,1] 即可，可以看作把一个极长段“拍扁”了，这样就能节省一步，可以“拍扁”的充要是对于第一个极长段的结为 l 和最后一段的开头 r，需满足 r-l\le a_r-a_l，即有足够的位置放下所有的数。

记得特判 c=1。

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005];
void Main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int cnt=0,op=0,lx=0,rx=0;
    for(int i=1;i<n;i++)
        if(a[i]>a[i+1])
            cnt++;
    for(int i=1;i<n;i++)
        if(a[i]>a[i+1])
        {
            if(!lx)
                lx=i;
            rx=i+1;
        }
    if(cnt==1)
    {
        cout<<"1\n";
        return;
    }
    if(cnt%2==0&&rx-lx-1>a[rx]-a[lx]-1)
        op=1;
    cout<<(cnt+1)/2+op<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)Main();
    return 0;
}