Codeforces-1617-C Paprika and Permutation

题目大意

给定一个\(n(1\le n \le 10^5)\)个数的正整数数组\(a_n(1 \le a_i \le 10^9)\),你需要把它变成一个\(1\)~\(n\)的排序,可选的操作只有: 对于\(a_i\),选择一个正整数\(x(1 \le x \le a_i)\),令\(a_i = a_i \% x\)。

问是否可以通过任意次这种操作是数组\(a\)成为一个排列。 题目链接

思路

对于\(a_i\)，它能变成的最大的数就是\(\lfloor \frac{a_i}{2} \rfloor\)。 那么我们的贪心思路就是:对于新排列中的数\(a_i'\)，我们尽可能选择原序列中小的数去生成它。 但是，还是有一个隐藏条件我们没有发现，那就是假如在原序列中\(1 \le a_i \le n\)，那么它本身就已经在排列中了，那么我们会选择不去操作这个数。

证明: 根据前面说的，它能生成的新数在\([1,\lfloor \frac{a_i}{2} \rfloor\)]。中，假设原序列中有个数\(a_k\),它能生成\(a_i\)，那么\([1,\lfloor \frac{a_i}{2} \rfloor\)]之间的数它也能生成,所以这么做不会使得结果更劣。 并且，有可能\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/02/01/Codeforces-1617-C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！