【C++】ABC396 C.Buy Balls 解説

はじめに

こんにちは！競技プログラミングをやっている学生のmikan0131です！
今回は久しぶりにAtCoderの解説をしていこうと思います！

問題文

要するに、一番価値が高くなるように黒・白のボールを選べ、でも黒の数$\ge$白の数だよってことみたいです。
それでは、解いていきましょう。

解説

とりあえず、必要な値を入力しましょう。

#include <bits/stdc++.h>
using namespace std;

int N, M;
int B[200009], W[200009];

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> B[i];
    for (int j = 1; j <= M; j++) cin >> W[i];
    return 0;
}

ひとまず、ここまでで入力は終了です。
では、ここからどうしましょうか？

まず、当たり前の話ですが、価値の値が負のボールを選ぶと、価値の総和は下がりますし、正のボールを選ぶと、価値の総和は上がります。なので、できれば価値の値が正のボールを全部選びたい！
しかし、ここで問題になるのは、問題の条件である「(黒のボールの個数)$\ge$(白のボールの個数)」というところです。
もし、正の価値のボールをすべて選んでも、その時に選んだ黒のボールの数が白のボールの数より多かったら条件は成り立たなくなってしまいます。
それなら、どうすればいいのでしょうか？さすがに全部試すのも間に合わないし…
そこで、思いついたのが黒、白どちらのボールの価値もソートしてから、二つ同時に大きい順から試すという方法です。
どういうことかというと、配列$B$・$W$をソートかつリバースし、大きい順に並べます。
そして、大きいほうから順に黒と白の価値を同時にみていって、下の図のような条件で価値を決める方法です。
どちらも正の価値の時は当然それらのボールの価値の和答えにを足す。
黒が負の価値の時は、白の正の価値を足すために黒のボールも追いつく必要がありますが、それで価値がマイナスになると本末転倒なので、黒と白の価値の和が正の時だけ答えに足す。
白が負の価値の時は、黒だけ足せば問題ないので、黒の価値を足す。
さらに、どちらも負の時は当然どちらも足さない。

このようにしてみていけば、$O(N)$で答えを求めることができます。

解答

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//値がint型におさまらない（おさまるわけない）ので、long long型にする

ll N, M;
ll B[200009], W[200009];

int main() {
    //入力
    cin >> N >> M;
    for (ll i = 1; i <= N; i++) cin >> B[i];
    for (ll i = 1; i <= M; i++) cin >> W[i];
    //B, Wをソート
    sort(B + 1, B + N + 1);
    sort(W + 1, W + M + 1);
    reverse(B + 1, B + N + 1);
    reverse(W + 1, W + M + 1);
    ll ans = 0;
    //解説のように条件分岐をしながら見ていく（途中breakがあるのは余計な計算を省くためで、正直なくてもいい）
    for (ll i = 1; i <= N; i++) {
        if (B[i] >= 0 && W[i] >= 0) {
            ans += B[i] + W[i];
        }
        else if (B[i] >= 0 && W[i] < 0) {
            ans += B[i];
        }
        else if (B[i] < 0 && W[i] >= 0) {
            if (B[i] + W[i] >= 0) {
                ans += B[i] + W[i];
            }
            else {
                break;
            }
        }
        else {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

おわりに

読んでくれた方、ありがとうございました！
解説、わかりにくかったらごめんなさい
この解説で分かってくれた人はこの解説をupsolvingに役立ててくれたらうれしいです！
ありがとうございました！