Exam and Wizard [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 C]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c

解説

https://atcoder.jp/contests/keyence2019/submissions/4015448

貪欲に構成していく。
最初はC[i]=B[i]とする。
この段階でCの和smBがsmAを上回っていれば、構築できないので、-1
　
次にd=smA-smBの分をC[i]に足しながら補っていくが、基本的にはC[i]=A[i]となるようにしたい。
なので、A[i]とB[i]の関係性をまずはカウントしよう。
ng := A=Cにできない添字の個数
up := A=Cにするために必要な差分の配列
same := A=Cである添字の個数
A[i] < B[i]なら、どうやってもA[i]=C[i]にできないので、ng++;
B[i] < A[i]なら、差分A[i] - B[i]だけA=Cとできるので、upに追加
Ai] = B[i]なら、same++
　
あとはdをうまく使って、upをなるべくsameにしていきたいが、必要な差分が小さい方から順番にやっていくのがいい。
upをソートして、順番に処理していこう。
　
dが余った場合はそれをどこかに押し付けるが、ans=0のときは押し付け先が無いため、答えが1つ増える。

int N; 
ll A[101010], B[101010];
ll C[101010];
int vis[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
 
    ll smA = 0;
    rep(i, 0, N) smA += A[i];
 
    int ans = 0;
    rep(i, 0, N) C[i] = B[i];
    
    ll smB = 0;
    rep(i, 0, N) smB += B[i];
 
    if (smA < smB) {
        printf("-1\n");
        return;
    }
 
    ll d = smA - smB;
    vector<pair<int,int>> up;
    int ng = 0;
    int same = 0;
    rep(i, 0, N) {
        if (A[i] < B[i]) ng++;
        else if (B[i] < A[i]) up.push_back({ A[i] - B[i],i });
        else same++;
    }
 
    sort(all(up));
    fore(p, up) {
        if (p.first <= d) {
            d -= p.first;
            C[p.second] = A[p.second];
        }
    }
 
    rep(i, 0, N) if (A[i] != C[i]) ans++;
    if (d) {
        if (ans == 0) ans++;
    }
    
    cout << ans << endl;
}