はまやんはまやんはまやん

hamayanhamayan's blog

Views Matter [Codeforces Round #523 (Div. 2) B]

競技プログラミング

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

横Nマス、縦Mマスの盤面がある。
各列A[i]個のマスが下詰めで塗られている。
これを上から見た眺めと横から見た眺めがどちらも変わらないように塗られているマスを消す。
最大何マス消せるか。

解説

http://codeforces.com/contest/1061/submission/46096214

ソートしても眺めは変わらないのでする。


あとはsatanicさんのこの画像のように階段式に塗っていけばいい。
多く塗られている列の方が臨機応変にできるので、少ない方からなるべく上に上がっていくようにしていけばいい。

int N, M; int A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
    
    ll ans = 0;
    rep(i, 0, N) ans += A[i];

    int prev = 0;
    rep(i, 0, N) {
        ans--;
        if (prev < A[i]) prev++;
    }
    ans -= A[N - 1] - prev;
    cout << ans << endl;
}