GCJ 2015 Round 1B B. Noisy Neighbors

2015/05/03 (Sun) GCJ 貪欲 場合分け

問題

問題文

$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);
    }
}