题解：CF1617C Paprika and Permutation

__Clannad__ · 2025-02-16 11:36:49 · 题解

原题

题目给一个数组 a_1,a_2,\dots,a_n。每次操作可以选择数组中的一个元素 a_i 并自选一个数 x，将 a_i 变为 a_i \bmod x。

思路

一道十分不错的贪心题。

一种容易想到的思路是：将需要调整和未被使用的元素一一拿出来，暴力匹配。

但这种方法的复杂度为 \mathcal{O}(n^2) ，显然会超时。

决策具有后效性，因此考虑贪心。

令 extra_i 表示需要调整的元素，target_i 表示未被使用的目标数。

容易发现，若 target_i 无法通过 extra_j \bmod x 的方式得到，那么 extra_j \leq 2 \times target_i。

现在，我们要想办法尽可能的让 extra_j > 2 \times target_i。

一种贪心策略是：将 extra 和 target 分别排序，一一判断。

容易证明，若排序后的 target_i 和 extra_i 无法满足要求，则此样例无解。

具体细节看代码。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005];
bool used[100005]; // 记录1~n中已存在的数
int solve(int n) {
    memset(used,false,sizeof(used));
    vector<int> extra; // 需要调整的元素
    for (int i=0;i<n;i++) {
        if (a[i] >= 1 && a[i] <= n && !used[a[i]]) {
            used[a[i]] = true;
        } else {
            extra.push_back(a[i]);
        }
    }
    vector<int> target; // 未被使用的目标数
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            target.push_back(i);
        }
    }
    // 如果数量不匹配，无法调整
    if (extra.size() != target.size()) {
        return -1;
    }
    // 排序后贪心匹配
    sort(extra.begin(), extra.end());
    sort(target.begin(), target.end());
    for (int i = 0; i < (int)extra.size(); ++i) {
        if (extra[i] <= 2 * target[i]) {
            return -1;
        }
    }
    return extra.size();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        cout << solve(n) << '\n';
    }
    return 0;
}

时间复杂度 \mathcal{O}(tn \log n) ，本题中 \sum{n} \leq 2 \times 10^5，可以通过本题。