けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

キーエンス プログラミング コンテスト 2019 C - Exam and Wizard (400 点)

好き!!!

問題へのリンク

問題概要

長さ  N の 2 つの数列  A_1, A_2, \dots, A_N B_1, B_2, \dots, B_N が与えられる。

数列  C_1, C_2, \dots, C_N であって

  • 任意の  i に対して、 C_i \ge B_i
  •  C_1 + C_2 + \dots + C_N = A_1 + A_2 + \dots + A_N

を満たすものを考えたときの、 A_i \neq C_i となる  i の個数の最小値を求めよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

 A をなるべく変形箇所を少なくしつつ  C に変形して、 B にオール勝ちできるようにする問題。

ここで、 B の値そのものはそんなに重要じゃなくて、 A B との差だけが重要 (例えば、 A_2 = 3, B_2= 5 だったとして、これは  A_2 = -2, B_2 = 0 でも状況はまったく変わらない) なので、 B は全部  0 にしてしまう。そうすると

 A = {-9, -6, -4, -1, 0, 0, 2, 5, 7, 9, 11}

みたいな感じになる。これに対して、 A の総和を変えずに、なるべく変更を加える箇所を少なくして、マイナスをなくす問題になる。

ただちにわかることは

  • マイナスは埋め立ててすべて  0 にしなければならない

よって、マイナスの箇所は必ず変更が加えられることになる。このとき、 A の値が正の部分から削ってマイナスを埋め立てることになる。よって、正の部分を削る箇所を少なく抑えるには、なるべく値の大きなところから優先的に削って行くのがいい。

  • このとき、すべての正の値を使い尽くしてもマイナスを消せなかった場合は  -1 ( A の総和がマイナスの場合)
  • マイナスがなかった場合は答えは  0

という点に注意する。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];
        
    vector<long long> plus;
    long long sum = 0;
    int num = 0;
    for (int i = 0; i < N; ++i) {
        long long dif = A[i] - B[i];
        if (dif < 0) sum -= dif, ++num;
        else plus.push_back(dif);
    }
        
    if (num == 0) cout << 0 << endl; // マイナスがなかったら変更の必要なし
    else {
        int res = num;
        sort(plus.begin(), plus.end(), greater<long long>());
        
        // 正の部分のうち、大きい方から優先的に削ってマイナスを埋め立てる
        long long p = 0;
        for (int i = 0; i < plus.size(); ++i) {
            p += plus[i];
            ++res;
            if (p >= sum) break;
        }
            
        if (p >= sum) cout << res << endl;
        else cout << -1 << endl;
    }
}