abc063 D - Widespread（400点）
初めて決め打ち二分探索をやった
決め打ち二分探索って？
決め打ち二分探索とは、「条件を満たす$ Xの最大値・最小値」を求める時に、
1：絶対に条件を満たす数 $ X_aと絶対に条件を満たさない数$ X_bを最初に変数にとり、その平均$ X_mをとる
2：$ Xが$ X_mの時に、条件を満たすならば、$ X_aに、条件を満たさないならば$ X_bに$ X_mを代入する。
3：2の操作を$ X_aと$ X_bの差が1になるまで繰り返す。
4：このときの$ X_aが「条件を満たす$ Xの最大値・最小値」になる。
という方法で求めていくもの。
今回は、$ X_mが与えられたときには、最初に全員の体力を$ X_m \times Bだけ減らしておいて、あと何回$ B - Aの攻撃をすればいいかを調べて、それが$ X_m以下なら条件を満たしている、$ X_mより大きいのなら条件を満たしてない、という正誤判定をすればよい。
code:hoge.cpp
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;
int main() {
int N,A,B;
cin >> N >> A >> B;
A -= B;
vector<ll> vec(N);
for(int i = 0;i < N;i++) {
cin >> vec.at(i);
}
ll ng = 0; //条件を絶対に満たさない値
ll ok = 10000000000; //条件を絶対に満たす値
ll middle; //okとngの平均
while(ok - ng > 1) {
middle = (ok + ng) / 2;
vector<ll> cnt = vec;
for(int i = 0;i < N;i++) {
cnt.at(i) -= middle * B;
}
ll cnt2 = 0;
for(int i = 0;i < N;i++) {
cnt2 += max(0ll,(cnt.at(i) + A - 1) / A);
}
if(cnt2 <= middle) {
ok = middle;
}
else {
ng = middle;
}
}
cout << ok << endl;
}