题解：P13463 [GCJ 2008 #1C] Text Messaging Outrage

furina_yyds · 2025-07-27 11:35:45 · 题解

题解：P13463 [GCJ 2008 #1C] Text Messaging Outrage

这是一道贪心水题。

思路

要使得总次数最少，优先要将频率高的字母放在按键前面，所以可以将字母按频率排序，前 1 \sim k 大的字母放在所有按键的第一个，前 k+1 \sim 2k 大的字母放在所有按键的第二个，以此类推。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, p, k, l, a[1005];
long long ans;
int main(){
    scanf("%d", &n);
    for(int _ = 1; _ <= n; _++){
        scanf("%d%d%d", &p, &k, &l);
        ans = 0;
        for(int i = 1; i <= l; i++){
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + l + 1, greater<int>());
        for(int i = 1; i <= l; i++){
            ans += a[i] * ((i + k - 1) / k);
        }
        printf("Case #%d: %lld\n", _, ans);
    }
    return 0;
}