专栏文章

CF2144B Maximum Cost Permutation

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minsua5v
此快照首次捕获于
2025/12/02 07:47
3 个月前
此快照最后确认于
2025/12/02 07:47
3 个月前
查看原文

题目传送门

思路

首先我们先增加一个特判：如果在整个序列中只有 11 个空缺，那么只能将唯一一个排列中缺失的数填到那个空缺中，此时就是一个完整的排列。
如果我们想让这个排列的代价最大，那么我们需要使得这个满足条件的子段的最左端点和最右端点放上的数不是它自身。
此时可以放一个左端点和右端点，左端点从 11 开始，并且从左至右遍历，当碰到一个数与它的下标不同时停止遍历；右端点从 nn 开始，并且从右至左遍历，同样当碰到一个数与它的下标不同时停止遍历。这时 [l,r][l,r] 这一区间就一定是排列中需要排序的连续子段中最长的。
关键代码：
CPP
int l=1,r=n;
//注意保证不越界
while(l<=n && a[l]==l) l++;
while(r>=1 && a[r]==r) r--;
但此时不能直接输出 r−l+1r-l+1。如果此时的 ll 和 rr 全都走到了头，那么这时的答案应该为 00，但此时的程序会输出一个负数，所以最终的答案应该为 00 和 r−l+1r-l+1 的最大值。

AC Code：

CPP
#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;
}

评论

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

正在加载评论...