【Codeforces】1617C Paprika and Permutation 题解

题目大意

给定 $n$（$1 \le n \le 10^5$）个数的数组 $a_n$（$1 \le a_i \le 10^9$），可以对 $a_i$ 选择一个正整数 $x$（$1 \le x \le a_i$），令 $a_i = a_i \bmod x$。

问是否可以通过任意次这种操作使数组 $a$ 成为 $1 \sim n$ 的一个排列。

题目链接

思路

通过操作，$a_i$ 能生成的最大值为 $\lfloor \frac{a_i}{2} \rfloor$（取 $x = \lfloor \frac{a_i}{2} \rfloor + 1$ 时取到最大余数）。

我们的贪心思路是：对于新排列中需要被生成的数 $i$，尽可能选择原序列中最小的可用数去生成它。

还有一个隐藏条件：假如在原序列中 $1 \le a_i \le n$，那么这个数可以直接留在原位，不应当去生成其他数。

证明：根据前面说的，$a_k$ 能生成 $a_i$，那么 $a_k$ 也能生成 $[1, \lfloor \frac{a_k}{2} \rfloor]$ 范围内的数，因此 $a_k$ 完全可以代替 $a_i$ 去完成生成任务。

并且，有可能 $a_i$ 本身无法被生成，比如 $[2, 3, 5]$ 这种情况，如果让 $3$ 去生成 $1$ 了，那么 $3$ 这个数就无法填充了，所以正确做法是 $2, 3$ 不变，让 $5$ 去生成 $1$。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxN = 1e5 + 7;

int T, n, a[maxN], matched[maxN], used[maxN];
//matched[i]表示新排列中i这个数是否已经被生成，used[i]表示原序列中a[i]是否被使用过了
int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sort(a + 1, a + 1 + n);
        int ans  = 0;
        memset(matched, 0, sizeof matched);
        memset(used, 0, sizeof used);
        for(int i = 1; i <= n; ++i)
            if(a[i] >= 1 && a[i] <= n && matched[a[i]] == 0) {
                matched[a[i]] = i;
                used[i] = 1;
            }
        int u = 1; bool succ = true;
        for(int i = 1; i <= n; ++i) {
            while(used[u]) u++;
            if(matched[i])
                continue;
            if((a[u] + 1) / 2 <= i && a[u] != i) {
                succ = false;
                break;
            }
            used[u] = 1;
            matched[i] = u;
            ans++;
        }
        if(!succ)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}