[ARC144] B - Gift Tax

[Q] https://atcoder.jp/contests/arc144/tasks/arc144_b

求めたい値で、にぶたんするだけ。

入力例2
N=3 a=2 b=3
A[]: 11 1 2

・ans=10 と仮定した場合、a操作とb操作の必要回数を求めていく。
A[0]-10 = 11-10 = +1なので、1/3 = 0回b操作できる。(できない)
A[1]-10 = 1-10 = -9なので、(9+(a-1))/a = 10/2 = 5回a操作が必要。
A[2]-10 = 2-10 = -8なので、(8+(a-1))/a = 8/2 = 4回a操作が必要。

b操作が0回、a操作が9回、は成立しないので、10は大きすぎ。

bが余る分には問題がないので、b操作>=a操作のとき、解答を満たす。

・ans=4 と仮定した場合、a操作とb操作の必要回数を求めていく。
A[0]-4 = 11-4 = +7なので、7/3 = 2回b操作できる。
A[1]-4 = 1-4 = -3なので、(3+(a-1))/a = 4/2 = 2回a操作が必要。
A[2]-4 = 2-4 = -2なので、(2+(a-1))/a = 3/2 = 1回a操作が必要。

Bcnt=2 < Acnt=3 なのでダメ。

・ans=3 と仮定した場合、a操作とb操作の必要回数を求めていく。
A[0]-3 = 11-3 = +8なので、8/3 = 2回b操作できる。
A[1]-3 = 1-3 = -2なので、(2+(a-1))/a = 3/2 = 1回a操作が必要。
A[2]-3 = 2-3 = -1なので、(1+(a-1))/a = 2/2 = 1回a操作が必要。

Bcnt=2 >= Acnt=2。Bcntに余裕があるケースなのでOK。

ans = 3

・実装

 

int main() {
 ll N, a, b;
 cin >> N >> a >> b;
 ll A[N];
 ll ans = 0;
 rep(i, N) cin >> A[i];

 // 二分探索
 ll high = 1e9 + 10000;
 ll low = 0;
 while (high - low > 1) {
   ll Acnt = 0;
   ll Bcnt = 0;
   ll mid = (high + low) / 2;
   // 引く数と、タス数をだす
   rep(i, N) {
     ll dif = A[i] - mid;
     if (dif > 0) { // 何回Bしていいか。余裕度
       Bcnt += dif / b;
     } else { // 何回Aする必要があるか。必要度
       Acnt += (abs(dif) + a - 1) / a;
     }
   }
   // Bが余る分にはかまわない
   if (Bcnt >= Acnt) {
     low = mid; // lowが解答になる
   } else
     high = mid;
 }
 cout << low << endl;
}

https://atcoder.jp/contests/arc144/submissions/33260937