(COCI 2017/2018 5) Karte

题解

题意

有 N 张牌，从顶部到底部排列。第 i 张牌上有一个数字 aᵢ，表示它下方的牌中至少有 aᵢ 张牌的信息是错误的。

判断一张牌是否正确：若它下方确实有至少 aᵢ 张错误牌，则该牌信息正确；否则该牌信息错误。

（最底部的牌下方有 0 张牌，因此若 aᵢ > 0 则必定错误。）

现需要重新排列这 N 张牌，使得恰好有 K 张牌的信息是错误的。若存在方案，输出任意一种从顶部到底部的排列；若不存在，输出 -1。

数据范围

• 1 ≤ N ≤ 5 × 10⁵
• 0 ≤ K ≤ N
• 0 ≤ aᵢ ≤ 5 × 10⁵

解法

神秘思维题。

首先我们分析题意，对于一张牌他的信息时错误的，当且仅当前面错误牌的个数$< a_i$。而题目要求错误牌的数量为$K$个

很显然对于存在构造方案有一个必要条件是$a_i > K$的牌的数量$\leq K$。说起来可能有点绕，总之就是因为我们要求错误的牌能有$K$ 个所以对于那些$a_i>K$的牌来说他们一定是错误的。而如果这样的牌$> K$个那么就与错误牌的数量为$K$个冲突了。

再思考我们会发现，我们把这些前$K$大的牌按照从小到大的顺序放在底部是优秀的。因为$a_i$越大，越不容易满足正确，就越容易错误。我们可以用反证法，如果说把前K大的牌放在底部都无法满足要求的话，那么存在两种情况。

$1.$错误的牌少了，但是我们已知前$K$大的牌一定是大于其他牌的，那么竟然更大的牌都一定会满足条件，那么更小的牌就更会满足条件，无论如何替换，都不可能让错误牌数量增加，如果真的出现这种情况，只能说明这是无解的。

$2.$错误的牌多了，这说明除了这$K$个错误牌以外还有其他牌无法满足条件，而我们已知这前$K$大的牌错误，那么剩下的更小牌若是无法满足条件只能说明这个牌$a_i>K$那么就出现了最开始讨论的无解情况

至于为什么要让这些牌按照从小到大的顺序排列，因为越小的牌放在越后就越容易正确，而我们的目标是让这$K$张牌全部错误，所以按照从小到大的顺序排列一定是不劣的。

因此这个贪心是正确的，实际代码十分简洁。时间复杂度$O(n \log n)$

代码

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k;
int a[N];
int cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>k) cnt++;
    } 
    if(cnt>k)
    {
        cout<<-1;
        return 0;
    }
    sort(a+1,a+n+1);
    int j=0;
    for(int i=n-k+1;i<=n;i++)
    {
        if(a[i]<=j) 
        {
            cout<<-1;
            return 0;
        }
        j++;
    }
    for(int i=1;i<=n-k;i++) cout<<a[i]<<' ';
    for(int i=n;i>=n-k+1;i--) cout<<a[i]<<' ';
    return 0;
}