专栏文章

题解：CF2144B Maximum Cost Permutation

NNEKO_Daze
CF2144B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minv6asg
此快照首次捕获于
2025/12/02 08:52
3 个月前
此快照最后确认于
2025/12/02 08:52
3 个月前
查看原文
洛谷CF2144B || CodeForces 2144 B

简要题意

定义一个排列的代价为：满足条件的最短子段长度，使得对其进行排序后整个排列变为递增有序。
现在有一个由若干个 00 和 [1,n][1,n] 中两两不相同的正整数组成的数组 pp，请将其所有 00 改为某个整数，使得 pp 为一个排列且代价最大。

思路

我们要构造 [1,n][1,n] 的数的排列，也就是选取一段子段，使得里面包含所有不在正确位置上的元素，那么该子段的左右端点就是最左、最右的不在正确位置上的元素。
如果我们只有一个 00，那么我们只有一种选择，直接填入缺失元素计算即可。
而如果有多个 00，那么我们可以让每一个 00 最后改为的数都不在其正确位置上，以追求最短子段更大，这样代价也越大。
时间复杂度为 O(n)O(n)。
CPP
#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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...