题解：CF2144B Maximum Cost Permutation

NEKO_Daze · 2025-09-18 15:45:36 · 题解

洛谷CF2144B || CodeForces 2144 B

简要题意

定义一个排列的代价为：满足条件的最短子段长度，使得对其进行排序后整个排列变为递增有序。

现在有一个由若干个 0 和 [1,n] 中两两不相同的正整数组成的数组 p，请将其所有 0 改为某个整数，使得 p 为一个排列且代价最大。

思路

我们要构造 [1,n] 的数的排列，也就是选取一段子段，使得里面包含所有不在正确位置上的元素，那么该子段的左右端点就是最左、最右的不在正确位置上的元素。

如果我们只有一个 0，那么我们只有一种选择，直接填入缺失元素计算即可。

而如果有多个 0，那么我们可以让每一个 0 最后改为的数都不在其正确位置上，以追求最短子段更大，这样代价也越大。

时间复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> p(n), pos0, book(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        --p[i];
        if(p[i] == -1)
            pos0.push_back(i);
        else
            book[p[i]] = 1;
    }
    if(pos0.size() == 1) 
    {
        int flag = 0;
        for(int i = 0; i < n; i++) if(book[i] == 0) flag = i;
        p[pos0[0]] = flag;
    }
    int l = 0, r = n - 1;
    while(l < n && p[l] == l) l++;
    while(r >= 0 && p[r] == r) r--;
    cout << max(0, r - l + 1) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;   
    for(int i = 0; i < t; i++)
        solve();
}