読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Google Code Jam 2008 Round 1C : A. Text Messaging Outrage

さて1Cも解いていきます。
まだ1問めなので難易度は低め。
http://code.google.com/codejam/contest/32015/dashboard#s=p0

携帯電話風の文字入力において、各アルファベットのキーへの割り当てを変えられる。
各アルファベットの登場回数が与えられたときに、総キー押下回数を最小化する問題。

キーがK個あるので、登場回数の多い最初のK種の文字はキー1回で出せ、次に多いK種は2回で出せ…と割り当てればよい。
結局i番目(0-origin)に多いキーは(1+i/K)回押せばよい。

int P,K,L;
int F[1001];

void solve(int _loop) {
	int i,j,k,l;
	s64 res = 0;
	
	GET3(&P,&K,&L);
	FOR(i,L) F[i]=GETi();
	sort(F,F+L);
	reverse(F,F+L);
	
	FOR(i,L) res += F[i]*(1+i/K);
	
	_PE("Case #%d: %lld\n",_loop,res);
}

まとめ

STLのsortやreverseは配列にも使えるので楽ですね。

広告を非表示にする