CF2144B Maximum Cost Permutation

Andy1101 · 2025-09-24 19:51:52 · 题解

题目传送门

思路

首先我们先增加一个特判：如果在整个序列中只有 1 个空缺，那么只能将唯一一个排列中缺失的数填到那个空缺中，此时就是一个完整的排列。

如果我们想让这个排列的代价最大，那么我们需要使得这个满足条件的子段的最左端点和最右端点放上的数不是它自身。

此时可以放一个左端点和右端点，左端点从 1 开始，并且从左至右遍历，当碰到一个数与它的下标不同时停止遍历；右端点从 n 开始，并且从右至左遍历，同样当碰到一个数与它的下标不同时停止遍历。这时 [l,r] 这一区间就一定是排列中需要排序的连续子段中最长的。

关键代码：

int l=1,r=n;
//注意保证不越界
while(l<=n && a[l]==l) l++;
while(r>=1 && a[r]==r) r--;

但此时不能直接输出 r-l+1。如果此时的 l 和 r 全都走到了头，那么这时的答案应该为 0，但此时的程序会输出一个负数，所以最终的答案应该为 0 和 r-l+1 的最大值。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
bool vis[N];
void solve()
{
    memset(vis,0,sizeof vis);
    int n;
    cin >>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin >>a[i];
        if(a[i]==0) cnt++;
    }
    if(cnt==1)
    {
        int p;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0)
            {
                p=i;
                break;
            }
        }
        for(int i=1;i<=n;i++) vis[a[i]]=1;
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0) a[p]=i;
        }
    }
    int l=1,r=n;
    while(l<=n && a[l]==l) l++;
    while(r>=1 && a[r]==r) r--;
    cout <<max(0,r-l+1)<<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}