专栏文章

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

ffurina_yyds
P13463题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopecvt
此快照首次捕获于
2025/12/02 22:59
3 个月前
此快照最后确认于
2025/12/02 22:59
3 个月前
查看原文

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

这是一道贪心水题。

思路

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

代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...