题解：P12015 [NOISG 2025 Finals] 怪物

__xxy_free_ioi__ · 2025-04-04 23:09:01 · 题解

P12015 [NOISG 2025 Finals] 怪物

毒瘤

解法

易得，此题为贪心。

我们来想想贪心的策略，首先，我们很显然的可以想到一个解法：在有怪物地雷肯定是要引爆的。计算每一只怪物移动到附近地雷的代价（加上引爆代价），如果它小于等于这只怪物的生命值 h_i，那么我们就选择移动并引爆，否则直接敲死即可。但是，这样明显是错误的，我们不应该将怪物移动到地雷上就引爆，应该看看有没有其他怪物也要移动到这里，一起引爆，能省更多的钱，那么我们就需要定义一个数组 st 来表示这里是否已经有怪物了。至于为啥是小于等于 h_i 呢，原因是你占一个地雷说不定可以让其他怪物更少花费便可以被杀死。而判断移动到附近地雷的代价，我们只要将 x 数组排序，使用 lower_bound 即可。

这样，我们的代码就初具雏形了，欸，交上去怎么只要 14 pts？仔细想想，发现是想漏了一种情况，比如说：

这种怪物处于中间（并且两边移动花费（包括引爆费用）相同，移动花费小于怪物生命值）的情况又怎么办呢？哦，我们应该将怪物的位置也进行排序，这样，前面的已经全部处理完了，我们只需要考虑后面的，自然是向后移动啦！

代码

理清了思路，代码就很好写了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

struct Monster {
    int a, h;
    bool operator< (const Monster& W) {return a < W.a;}
} monsters[N];

int n, k, res;
int x[N], st[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> monsters[i].a >> monsters[i].h;
    for (int i = 1; i <= k; i++) cin >> x[i];

    sort(x + 1, x + k + 1);
    sort(monsters + 1, monsters + n + 1);

    for (int i = 1; i <= n; i++) {
        int a = monsters[i].a;
        int p = lower_bound(x + 1, x + k + 1, a) - x;
        if (a == x[p]) st[p] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int a = monsters[i].a, h = monsters[i].h;
        int p = lower_bound(x + 1, x + k + 1, a) - x;
        int c1 = a - x[p - 1], c2 = x[p] - a,
            t1 = !st[p - 1], t2 = !st[p];
        if (p == 1) {
            if (c2 + t2 <= h) st[p] = 1;
            res += min(h, c2);
        } else if (p == k + 1) {
            if (c1 + t1 <= h) st[p - 1] = 1;
            res += min(h, c1);
        } else if (c1 + t1 < c2 + t2) {
            if (c1 + t1 <= h) st[p - 1] = 1;
            res += min(h, c1);
        }  else {
            if (c2 + t2 <= h) st[p] = 1;
            res += min(h, c2);
        }
    }

    for (int i = 1; i <= k; i++) 
        res += st[i];

    cout << res << '\n';

    return 0;
}