GCJ 2015 Round 1B B. Noisy Neighbors
問題
$R \times C$ のグリッドの各マスに $N$ 人の住人を配置する。 辺を共有する組の数を最小化したとき、その値はいくつか。
方針
隣り合うようなのマスの数が少ないマスから貪欲に埋めていく。 いくつかの通りに場合分けする方法もあるがこっちの方が圧倒的に楽。
実装
int solve(){
int H,W;
int N;
cin >> H >> W >> N;
int best = 1 << 29;
rep(times,2){
vector<int> neis;
rep(i,H)rep(j,W){
int nei = 0;
if((i+j)%2 == times){
if(i > 0) ++nei;
if(j > 0) ++nei;
if(i < H-1) ++nei;
if(j < W-1) ++nei;
}
neis.pb(nei);
}
sort(all(neis));
int ans = 0;
rep(i,N){
ans += neis[i];
}
best = min(best, ans);
}
return best;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
rep(i,T){
int ans = solve();
printf("Case #%d: %d\n", (int)i+1,ans);
}
}