题解：CF2057B Gorilla and the Exam

· · 题解

Gorilla and the Exam 题解

题目分析

题目要求我们对给定的数组进行至多 k 次修改操作，使得经过这些操作后，数组的函数 f(a) 能达到的最小值。函数 f(b) 表示将数组 b 变为空所需的最小操作次数。每次操作的方式是：选择一个连续子数组，并删除其中最小的元素及所有与最小值相等的元素。题目要求我们尽可能将数组变得更简化，即减少所需的操作次数。

解题思路

  1. 定义最小操作次数：在每次操作中，我们可以选择一个连续子数组，其中最小的值将被删除，同时删除所有等于这个最小值的元素。重复进行这样的操作直到数组为空。显然，数组中元素相同的部分可以通过一次操作删除，因此在做出修改时，目标是让数组中尽量多的元素相同，从而降低所需的操作次数。

  2. 修改的意义：我们最多可以修改 k 次，将数组中的某些元素修改为相同的数。通过这样的修改，可以使得尽可能多的元素相同，从而减少所需操作次数。

  3. 选择连续子数组 [l, r]：在计算 f(a) 时，我们需要删除某一连续子数组的所有最小值，显然选择整个数组 [l, r]（即 l = 1 且 r = n）是最不劣的策略，因为这样可以一次性将数组中的最小值全部删除。因此，我们的目标是尽量让数组中的某一个数字出现的次数最大化，以便减少操作次数。

  4. 优化方法：

    • 首先统计数组中每个元素的出现频率。
    • 对于每个出现的数字，我们希望通过最多 k 次修改操作，使得其他元素变成当前数字，使得相同的元素尽可能多。

  5. 特判处理：如果最终通过修改后的数组所有元素都相同，则只需要一次操作即可删除整个数组，因此需要特判这一情况，保证最后的答案正确。

复杂度分析

总时间复杂度：每个测试用例的时间复杂度为 O(nt)，考虑到总和约为 10^5，因此这个时间复杂度是可以接受的。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int T;
int x,n,k,d,ans,tmp,a[N];
map<int,int>cnt;
vector<int>l;

void solve() {
    cnt.clear();
    l.clear();
    memset(a, 0, sizeof(a));
    tmp = d = ans = 0;
    cin >> n >> k;

    // 读取数组并统计每个元素的出现频次
    for(int i = 1; i <= n; i++) {
        cin >> x;
        if(cnt[x] == 0) l.push_back(x);
        cnt[x]++;
    }

    // 将频次存入数组 a 中
    for(int i = 0; i < l.size(); i++) {
        a[++d] = cnt[l[i]];
    }

    // 对频次数组进行排序
    sort(a + 1, a + d + 1);

    // 初始化答案为数组长度
    ans = d;

    // 贪心选择最优答案
    for(int i = 1; i <= d; i++) {
        if(tmp + a[i] <= k) {
            tmp += a[i];
            ans--;
        } else {
            break;
        }
    }

    // 如果所有元素都被修改为相同，则答案为1
    if(ans == 0) ans = 1;

    cout << ans << '\n';
}

signed main() {
    cin >> T;
    while(T--) solve();
    return 0;
}

代码解释

  1. 输入读取：首先读取测试用例的数量 T，然后依次读取每组测试数据的数组长度 n 和最多可以修改的次数 k。接着读取数组 a。

  2. 频次统计：我们使用 map<int, int> 统计数组中每个数字的出现频次，并将每个不同数字存入 vector<int> l 中。

  3. 计算频次数组：将每个数字的出现频次存入数组 a，并对其进行排序。排序后的数组表示每个数字出现的频次。

  4. 贪心策略：通过贪心算法，从频次最小的开始累加，尝试将它们合并到一个数字中。累加的频次不能超过 k，每次成功合并时，答案减少一。

  5. 特判处理：在最后，如果通过修改操作后，所有元素都变为相同数字时，直接返回答案 1，表示只需要一次操作即可将整个数组删除。