CF1296D

题面

题目大意是:你和你的对手一起打小怪兽,$n$个小怪兽排成一排且各自有自己的血量,你和你的对手攻击力分别是$a$和$b$,回合制打怪兽,你先打然后轮到对手然后又轮到你以此类推,你和你的对手每打一下小怪兽会扣除攻击者攻击力的生命,如果最后你打死了怪兽你就能得到一分,如果对手打死了怪兽则你不得分(题目要求按顺序打怪兽)

并且作为一名科学家,你拥有一些特殊的科(外)技(挂),你的科技可以使用$k$次,每一次使用的可以跳过你对手的一个回合,现在问你你最多可以的多少分。

看到题目就想到贪心,首先打死每个怪物对得分的贡献都是1,假设打死第i个怪物你需要开挂 $h_i$ 次肯定是从$h_i$小的往大的打

其中(hp为怪物的血量)

代码就很好写了

1
#include <iostream>
2
#include <algorithm>
3
4
using namespace std;
5
6
const int maxn = 2e5 + 10;
7
8
int h[maxn];
9
10
int main() {
11
    int n, a, b, k;
12
    cin >> n >> a >> b >> k;
13
    for (int i = 1; i <= n; ++i) {
14
        cin >> h[i];
15
        h[i] %= a + b;
16
        if(h[i] == 0) h[i] = a + b;
17
        h[i] = int(h[i] / a) + (h[i] % a != 0) - 1;
18
    }
19
    sort(h + 1, h + 1 + n);
20
    int ans = 0;
21
    for (int i = 1; i <= n; ++i) {
22
        if(k - h[i] < 0) break;
23
        k -= h[i];
24
        ++ans;
25
    }
26
    cout << ans << endl;
27
    return 0;
28
}