自动搬运

查看原文

来自洛谷，原作者为

	B天选之子B 这家伙很懒，什么都没留下。

搬运于2025-08-24 22:02:17，当前版本为作者最后更新于2021-07-19 19:37:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

• 现在有一叠牌。

• 每张牌上有一个数字,表示它下面至少有几张牌上的信息是错误的。

• 如果下面没有那么多张牌是错的，那这张牌就是错的。

解题思路

• 首先是从最后一张牌开始往前推。

• 假定要求的错误牌都在最后，那么前面的都要是对的，否则就无解。

• 牌上记录的数中小的牌放在前面就有有可能是对的。

所以最后结论就是小牌在前面，大牌中又按从大到小排。

注意事项

1. 最后的大牌要单独排序。

2. 记录的是至少，不是刚刚好。

3. 方法有多种，输出一种就可以了，不用和样例一样。

奉上代码

#include <bits/stdc++.h>
using namespace std;
int A[500010],cw,n,k;//cw值的是错误个数
int cmp(int x,int y) { //从大到小排序 
	return x>y;
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++)scanf("%d",&A[i]);
	sort(A+1,A+n+1);        //先正着牌  
	sort(A+n-k+1,A+n+1,cmp);//后k个要倒着牌  
	for(int i=n; i>=n-k+1; i--)
		if(cw<A[i]) cw++;
	if(cw!=k||A[n-k]>k) { //错误个数不是k个就无解  
		printf("-1");
		return 0;
	}
	for(int i=1; i<=n; i++) printf("%d ",A[i]);
	return 0;
}

此题有些绕，多读几遍题目。