草体にぼ日記

だらだらと

キーエンスプログラミングコンテスト 2019 C Exam and Wizard

キーエンスプログラミングコンテスト 2019 C Exam and Wizard

提出AC

int main()
{
    cout <<setprecision(10);
    ll n ;cin >>n;
    int A[100100] , B[100100];
    rep(i,n) cin >> A[i];
    rep(i,n) cin >> B[i];

    ll sum_a = 0 , sum_b = 0;
    rep(i,n){
        sum_a += A[i];
        sum_b += B[i];
    }

    vector<ll> amari(0);
    ll yowaihito = 0;
    ll need = 0;
    rep(i,n){
        if(A[i] > B[i]){
            amari.push_back(A[i]-B[i]);
        }
        else if ( B[i] > A[i]) {
            yowaihito ++;
            need += B[i] - A[i];
        }

    }

    SORT(amari);
    rSORT(amari);

    if(sum_a < sum_b){
        cout << -1 <<endl;
        return 0;
    }
    else{
        //他では、最大でnだね。

        if(yowaihito==0){
            cout << 0 << endl;
            return 0 ;
        }
        ll count = 0;
        ll yasashi = amari[count];
        while(yasashi < need){
            count ++ ;
            yasashi += amari[count];
            //count + 1 個優しい人の力を借りる
            //足りてない人の数を足せば答え
        }
        cout << yowaihito + count+1  << endl;
        return 0 ;
    }
}

解法

まず、準備度が足りていないやつの個数その総和を求める

これが他からもらってこないといけない準備度なので、need っていう変数に入れておく。

そして、準備度が足りてゐないものの個数をyowaihito (弱い人なので)の変数に保持

弱い人は絶対A[i] != C[i] なので、答えに関連するよ

amari は、 A[i] > B[i] つまり、準備度が過剰なものの、差分を(準備度の余り)を入れていって、

それを 大きい順にソートする

準備度の余りが

100, 5 , 3 ,1 みたいな感じだった時、

100のものを使って弱い人達に分け与えていった方が良くて、

100が足りなら5も。って感じにしていくのが良いので大きい順にソートする

変数yasashi は amari の和でそれが need を超えたとき

amari っていう配列から何個の要素を使ったかが count + 1 に入っている。

  • 例外

    どうやっても無理なのは、Aの準備度の和がBの準備度の和に及ばないとき無理