D. Fight with Monsters

• Quiz
  • https://codeforces.com/problemset/problem/1296/D
• AC
  • https://codeforces.com/contest/1296/submission/88831779
• 解説
  • 各モンスターをAの手番で倒すためには魔法を何回使うことが必要か求めておく
  • その回数の配列を昇順ソートして、K以内に収まる限り採用すればいい
  • モンスターは左から倒していかないといけないけれど、ソートしてよいというのがポイントですね
• その他
  • 1500にしては簡単

int main(){
    // input
    ll N,A,B,K;
    cin>>N>>A>>B>>K;

    VI H(N);
    rep(i, N) cin >> H[i];

    // 必要な魔法の回数
    auto f = [&](ll h){
      h %= (A+B);
      if(h==0) h+=A+B;
      if(h<=A) return 0LL;
      ll n = (h+A-1)/A; // Aで何回殴ればいいか
      return n-1;
    };

    // 回数配列
    VI V;
    for(ll h : H){
      ll num = f(h);
      V.push_back(num);
    }
    SORT(V);

    ll cnt=0;
    ll sum=0;
    rep(i,N){
      if(sum+V[i]>K){
        p(cnt);
        return 0;
      }else{
        sum += V[i];
        cnt++;
      }
    }

    p(N);
    return 0;
}