好き！！！

問題概要

長さ $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;
    }
}