2015-2016 ACM-ICPC NEERC : I. Lottery

これは今回一番簡単な問題。
http://codeforces.com/contest/589/problem/I

問題

N個のくじがあり、それぞれの値はC[i]である。
K人でこのくじを引く際、公平になるようC[i]中1～Kが同じ数登場するようにしたい。
それには最小何個のくじの値を書き換えればよいか。

解法

１人当たりN/K個当たりがあるようにしたい。
D(x)をC[i]中xの値が書き込まれたくじだとする。

N/K個から溢れた分を足りない分に回すと考えて、sum(max(0,D(x)-N/K))を求めればよい。

int N,K;
int C[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		C[x-1]++;
	}
	int ret=0;
	FOR(i,K) if(C[i]>N/K) ret+=C[i]-N/K;
	cout<<ret<<endl;
	
}

まとめ

ここらは簡単。