此题贪心（绕）

B天选之子B · 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;
}

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