题目分析
这是一道贪心的题目。
思路
1. 题目解释
我们需要将字母分配到按键上，每个按键最多可以放\(P\)个字母。字母的按键次数取决于其在按键上的位置。例如，第一个字母按一次，第二个字母按两次，依此类推。
2. 贪心思路
为了最小化总按键次数，应该将出现频率最高的字母分配到按键的第一个位置，次高频的字母分配到按键的第二个位置，依此类推。
3. 实现
- 统计每个字母出现的频率
- 将所以字母按频率大到小排序
- 将所有次数乘以按键要按次数，求出答案。
代码
#include<bits/stdc++.h>
#define ri register int
#define int long long
#define run_fast ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
signed main() {int T;cin >> T;for (ri x = 1; x <= T; ++x) {int P, K, L;cin >> P >> K >> L;vector<long long> freq(L);for (ri i = 0; i < L; ++i) cin >> freq[i];sort(freq.rbegin(), freq.rend());long long total = 0;for (ri i = 0; i < L; ++i) {int press = (i / K) + 1;total += freq[i] * press;}cout << "Case #" << x << ": " << total << endl;}return 0;
}