题解：CF2144B Maximum Cost Permutation

hccan1101 · 2025-11-08 08:41:22 · 题解

题目传送门

思路

我们容易发现由 1\sim n 组成的递增排列一定是 1 \sim n ，所以想使代价最大，就按照 n \sim 1 的顺序填满剩余的空。

代码实现

我们可以扫一遍有哪些数没被填，然后从大到小填这些数，最后找出无序序列的左端和右端就能算出代价了。

#include<bits/stdc++.h>
#define int long long
#define fin(a) freopen(a, "r", stdin)
#define fout(a) freopen(a, "w", stdout)

using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], v[N];
signed main(){
    int t;
    cin >> t;
    while(t--){
        int n, idx = 0, l = 0, r = -1;
        cin >> n;
        fill(a, a + n + 1, 0);
        fill(b, b + n + 1, 0);
        fill(v, v + n + 1, 0);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        for(int i = 1; i <= n; i++){
                b[a[i]] = 1;
        }
        for(int i = n; i >= 1; i--){
            if(!b[i]) v[++idx] = i;
        } 
//      for(int i = 1; i <= idx; i++) cout << v[i] << ' ';
//      puts("");
        for(int i = n; i >= 1; i--){
            if(!a[i]) a[i] = v[idx--];
//          cout << a[i] << ' ';
            if(a[i] != i){
                if(r == -1) r = i;
                l = i;
            }
        }
//      for(int i = 1; i <= n; i++) cout << a[i] << ' ';
//      puts("");
        cout << r - l + 1 << '\n' ;
    } 
    return 0;
}