战斗爽

根据题意我们可以直接模拟：

  1. 我们用 priority_queue 维护所有敌人的攻击力 atk 以及尚且存活的敌人的血量 alive，用数组 dead 记录敌人是否活着
  2. 直接在 while 循环里模拟每一轮：
    1. 从 alive 里根据规则取出一个敌人，结算伤害，更新其存活状态
    2. 接下来结算收到的伤害。从 atk 堆顶取出攻击力最大的，如果堆顶的敌人已经死亡，则弹出取下一个元素，直到堆顶的敌人是存活的。
Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using i64 = long long;

using M = std::tuple<int, int, int, int>; // hp, atk, id, times
using N = std::tuple<int, int>;           // atk, id

void run() {
    int n, u, k, hq;
    std::cin >> n >> u >> k >> hq;

    std::priority_queue<M, std::vector<M>, std::greater<M>> pq;
    std::priority_queue<N> atks;
    i64 atk = 0;
    for (i64 i = 0, a, b; i < n; i++) {
        std::cin >> a >> b;
        pq.push({b, a, i, 0});
        atks.push({a, i});
        atk = std::max(atk, a);
    }

    int cnt = 0;
    std::vector<int> dead(n, false);
    while (!pq.empty() and hq >= 0) {
        auto [hp, a, id, t] = pq.top();
        pq.pop();

        // attack it
        if (t < k) {
            if (t == 0) hp -= u;
            else hp -= u / 2;
            t++;

            if (hp <= 0) cnt++, dead.at(id) = true;
            else pq.push({hp, a, id, t});
        }

        while (!atks.empty()) {
            if (dead.at(std::get<1>(atks.top()))) atks.pop();
            else break;
        }
        atk = std::get<0>(atks.top());
        hq -= atk;
    }

    std::cout << cnt << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int T = 1;
    std::cin >> T;
    while (T--) run();

    return 0;
}

充实

手推注意到如果只有两个数 x<yx<y 的话，有解当且仅当 y−x=2ky-x=2^k.

然后考虑多个数的情况，假设 a1<a2<a3<a4…ama_1\lt a_2\lt a_3\lt a_4 \dots a_m，其差分为 di=ai+1−aid_i=a_{i+1}-a_i. 只要 gcd⁡(di)=2k\gcd(d_i)=2^k 就有解

Code
 
1

持家

考虑打 aa 折，减 bb 元，原价 PP 元，则有

(P−b)×a=Pa−ba<Pa−b (P-b)\times a=Pa-ba \lt Pa-b

所以我们应该总是先用打折券，再用减价券。时间复杂度为排序的 O(nlog⁡n)O(n\log n)

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using i64 = long long;

void run() {
    int P, n, k;
    std::cin >> P >> n >> k;

    std::vector<double> a, b;
    for (int i = 0, c, t; i < n; i++) {
        std::cin >> t >> c;
        if (t == 0) a.push_back(c * 1.0 / 10);
        else b.push_back(c);
    }

    std::sort(a.begin(), a.end()), a.insert(a.begin(), 1);
    std::sort(b.begin(), b.end(), std::greater()), b.insert(b.begin(), 0);

    for (int i = 1; i < a.size(); i++) a[i] *= a[i - 1];
    for (int i = 1; i < b.size(); i++) b[i] += b[i - 1];

    double ans = P;

    for (int i = 0; i <= k; i++)
        if (i < a.size()) ans = std::min(ans, a[i] * P - b[std::min(k - i, int(b.size()) - 1)]);

    std::cout << std::fixed << std::setprecision(2) << std::max(ans, 0.0) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int T = 1;
    std::cin >> T;
    while (T--) run();

    return 0;
}