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

Dual_Ego · 2025-07-28 17:06:32 · 题解

题目传送门

解析

观察题目，和标签不难发现：

• 一个字母出现频率越大，越应该把它放在一个按键的前面。比如设有两个字母的出现频率分别为 N,M，所处的按键位置分别为 N_{1},M_{1}，且有 N \lt M，则按的次数为 N \times N_{1} + M \times M_{1}，显然减小 M_{1} 的值比减小 N_{1} 的值要划得来（按得次数下降的快）。

为了保证尽量使频率大的字母在按键前面，我们应该先把所有按键的第一层先填满，然后是第二层、第三层……，不必使一个按键填满。（数据范围保证按键填的下所有字母）

这样我们只需给字母的频率排序即可，不需要有字母。

Code

#include <bits/stdc++.h>
using namespace std;
int n,a[1145],cnt;
bool cmp(int x,int y){
    return x>y;//从大到小 
}
int main(){
    cin >> n;
    cnt=n;//序号 
    while(n--){
        int p,k,l;
        cin >> p >> k >> l;
        memset(a,0,sizeof(a));//不要忘记初始化 
        for(int i=1;i<=l;i++) cin >> a[i];
        sort(a+1,a+l+1,cmp);
        long long ans=0,v=0,flag=0;
        for(int i=1;i<=p;i++){
            for(int j=1;j<=k;j++){
                ans+=a[++v]*i;//字母频率*所在位置 
                if(v==l){//v记录所填字母序号 当第v个字母填完后，跳出 
                    flag=1;
                    break;
                }
            }
            if(flag==1) break;
        }
        cout << "Case #" << cnt-n << ": " << ans << "\n";
    }
    return 0;
}

记录