题目传送门

解析

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

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

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

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

Code

CPP

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

记录

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

文章操作

题目传送门

解析

Code

相关推荐

评论

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