Gorilla and the Exam 题解

题目分析

题目要求我们对给定的数组进行至多

k

次修改操作，使得经过这些操作后，数组的函数

f(a)

能达到的最小值。函数

f(b)

表示将数组

b

变为空所需的最小操作次数。每次操作的方式是：选择一个连续子数组，并删除其中最小的元素及所有与最小值相等的元素。题目要求我们尽可能将数组变得更简化，即减少所需的操作次数。

解题思路

定义最小操作次数：在每次操作中，我们可以选择一个连续子数组，其中最小的值将被删除，同时删除所有等于这个最小值的元素。重复进行这样的操作直到数组为空。显然，数组中元素相同的部分可以通过一次操作删除，因此在做出修改时，目标是让数组中尽量多的元素相同，从而降低所需的操作次数。
修改的意义：我们最多可以修改 $k$ 次，将数组中的某些元素修改为相同的数。通过这样的修改，可以使得尽可能多的元素相同，从而减少所需操作次数。
选择连续子数组 $[l, r]$ ：在计算 $f(a)$ 时，我们需要删除某一连续子数组的所有最小值，显然选择整个数组 $[l, r]$ （即 $l = 1$ 且 $r = n$ ）是最不劣的策略，因为这样可以一次性将数组中的最小值全部删除。因此，我们的目标是尽量让数组中的某一个数字出现的次数最大化，以便减少操作次数。
优化方法：
- 首先统计数组中每个元素的出现频率。
- 对于每个出现的数字，我们希望通过最多 $k$ 次修改操作，使得其他元素变成当前数字，使得相同的元素尽可能多。
特判处理：如果最终通过修改后的数组所有元素都相同，则只需要一次操作即可删除整个数组，因此需要特判这一情况，保证最后的答案正确。

复杂度分析

总时间复杂度：每个测试用例的时间复杂度为

O(nt)

，考虑到总和约为

10^5

，因此这个时间复杂度是可以接受的。

代码实现

CPP

#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;
}

代码解释

输入读取：首先读取测试用例的数量 $T$ ，然后依次读取每组测试数据的数组长度 $n$ 和最多可以修改的次数 $k$ 。接着读取数组 $a$ 。
频次统计：我们使用 map<int, int> 统计数组中每个数字的出现频次，并将每个不同数字存入 vector<int> l 中。
计算频次数组：将每个数字的出现频次存入数组 a，并对其进行排序。排序后的数组表示每个数字出现的频次。
贪心策略：通过贪心算法，从频次最小的开始累加，尝试将它们合并到一个数字中。累加的频次不能超过 $k$ ，每次成功合并时，答案减少一。
特判处理：在最后，如果通过修改操作后，所有元素都变为相同数字时，直接返回答案 1，表示只需要一次操作即可将整个数组删除。

题解：CF2057B Gorilla and the Exam

文章操作

Gorilla and the Exam 题解

题目分析

解题思路

复杂度分析

代码实现

代码解释

相关推荐

评论

题解：CF2057B Gorilla and the Exam