キーエンスプログラミングコンテスト 2019 C Exam and Wizard
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の準備度の和に及ばないとき無理