专栏文章

题解：CF2144B Maximum Cost Permutation

hhccan1101
CF2144B题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minc898i
此快照首次捕获于
2025/12/02 00:02
3 个月前
此快照最后确认于
2025/12/02 00:02
3 个月前
查看原文
题目传送门

思路

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

代码实现

我们可以扫一遍有哪些数没被填，然后从大到小填这些数，最后找出无序序列的左端和右端就能算出代价了。
CPP
#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;
}

评论

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

正在加载评论...