WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #177 Div2 B "Polo the Penguin and Matrix"

問題

http://codeforces.com/contest/289/problem/B

N * M の整数の行列が与えられる。
上から下に向かって1~Nの行番号が、左から右に向かって1~Mの列番号が振られている。

行列のいずれかの要素1つをDだけ増やすか減らす操作が出来る。
行列の要素の値を全て同じにするための最小の操作の回数を出力せよ。
不可能であれば-1を出力せよ。

制約

1 <= N, M <= 100
1 <= D <= 10^4
1 <= 行列の要素 <= 10^4



考えた事

行列とか関係ないよなぁ
1行をいっぺんに変更できる・・とかないし

どれかの要素の数値に合わせればいいわけだ。
でも全探索するとO(N^2 * M^2)になってだめだな・・

要素をソートして、真ん中の数値に合わせればいいんじゃね(直感)

AC

わ~い


事後

例えば7つの要素があったとして、それをソートする。
f:id:Ekaing:20130403221117j:plain

真ん中の数値に合わせると下図の黄色い部分だけコストがかかる
f:id:Ekaing:20130403221153j:plain

1つ右の数値に合わせると下図の黄色い部分だけコストがかかる
f:id:Ekaing:20130403221223j:plain

コストが増えた部分を赤、減った部分を青とするとこんな感じに
f:id:Ekaing:20130403221255j:plain

真ん中から1つでもずらすと、
増える事はあっても減る事はない事がわかる。

よって真ん中の数値に合わせると決めてかかってOK!

要素数が偶数の場合は、真ん中の2つのどちらかでOK!
どっちをとってもコストは変わらないと思う。


ソースコード

int N, M, D;
vector<int> nums;

int main() {

    cin >> N >> M >> D;
    int n = N * M;
    nums.clear();
    for( int i = 0; i < n; i++ ){
        int t;
        cin >> t;
        nums.push_back( t );
    }
    sort( nums.begin(), nums.end() );

    int chk = nums[n / 2]; // 合わせる数値
    int ans = 0;
    for( int i = 0; i < n; i++ ){
        int sub = abs( nums[i] - chk );
        if( sub % D ){
            cout << -1 << endl;
            return 0;
        }
        ans += sub / D;
    }

    cout << ans  << endl;
}