Description
There are \(n\) monsters standing in a row numbered from \(1\) to \(n\). The \(i\)-th monster has \(h_i\) health points (hp). You have your attack power equal to a hp and your opponent has his attack power equal to b hp.
You and your opponent are fighting these monsters. Firstly, you and your opponent go to the first monster and fight it till his death, then you and your opponent go the second monster and fight it till his death, and so on. A monster is considered dead if its hp is less than or equal to \(0\).
The fight with a monster happens in turns.
You hit the monster by \(a\) hp. If it is dead after your hit, you gain one point and you both proceed to the next monster.
Your opponent hits the monster by \(b\) hp. If it is dead after his hit, nobody gains a point and you both proceed to the next monster.
You have some secret technique to force your opponent to skip his turn. You can use this technique at most \(k\) times in total (for example, if there are two monsters and \(k=4\), then you can use the technique \(2\) times on the first monster and \(1\) time on the second monster, but not \(2\) times on the first monster and \(3\) times on the second monster).
Your task is to determine the maximum number of points you can gain if you use the secret technique optimally.
Input
The first line of the input contains four integers \(n,a,b\) and \(k\) \((1≤n≤2⋅105,1≤a,b,k≤109)\) — the number of monsters, your attack power, the opponent's attack power and the number of times you can use the secret technique.
The second line of the input contains \(n\) integers \(h_1,h_2,…,h_n (1≤hi≤10^9)\), where hi is the health points of the \(i\)-th monster.
Output
Print one integer — the maximum number of points you can gain if you use the secret technique optimally.
题文翻译
我和基友去刷怪，有\(n\)只怪，我的攻击力为\(a\)点，我基友的攻击力为\(b\)点，每一次遇到怪的时候是回合制，我先打，打完我基友在打，可以对怪物造成等额攻击力的血量损失，如果怪死在我手上我加一分而如果死在我基友手上则我不得分。
我有一个可以使用\(k\)次的黑魔法，每次使用可以使基友跳过他的当前回合
问最终我能最多得到多少分
Analysis
简单的贪心处理，排个序即可，优先找到需要更少次需要黑魔法就可以使我得到这一分的怪（包括\(0\)次）。
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2020-02-04 21:39:16
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; //怪物总数
int a; //我的攻击力
int b; //队友攻击力
int k; //可跳过回合次数
int monster[200005];
cin >> n >> a >> b >> k;
int tol_atk = a + b;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
tmp %= tol_atk;
if (tmp == 0)
{
tmp = tol_atk;
}
monster[i] = tmp;
}
sort(monster, monster + n);
int point = 0;
for (int i = 0; i < n; i++)
{
if (k >= 1)
{
k -= (ceil((double)monster[i] / a) - 1);
point++;
if (k < 0)
{
point--;
break;
}
}
}
cout << point << endl;
return 0;
}