题解：CF1257D Yet Another Monster Killing Problem

hhhua · 2025-05-22 16:09:52 · 题解

很容易注意到一天要打最多的怪。 \ 接着考虑在一天中当前打到第 l 个怪（未打），将打掉到第 r 个怪，可行否？

• 对怪物， 若存在英雄 i，使得 s_i \geq r-l+1 且 p_i \geq \max_{i=l..r}{a_i}，则可行。（充要）

到这里其实可以做了呢，我们把英雄按 s 排个序，我们二分这个 r，那相当于在一个后缀里面查 p_i 最大值。

• 要得到 O(n) 算法，我们还得动点脑子。

既然可以二分答案，那能不能增量式？因为查询不依赖 l、r，那其实这个过程是非常重复的，那我们可以预处理出 bst_r = \max_{s_i=r..n} p_i，对每天从 l 开始循环到可行条件不成立即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int T, n, m;
int a[N], p[N], s[N], bst[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) bst[i] = 0, cin >> a[i];
        cin >> m;
        for (int i = 1; i <= m; i ++ ) cin >> p[i] >> s[i], bst[s[i]] = max(bst[s[i]], p[i]);
        for (int i = n - 1; i; i -- ) bst[i] = max(bst[i], bst[i + 1]);
        int res = 0;
        for (int r = 1, l = 1; l <= n; res ++ , l = r) {
            if (bst[1] < a[r]) { res = -1; break; } 
            int maxv = a[r];
            while (r <= n && maxv <= bst[r - l + 1]) maxv = max(maxv, a[ ++ r]);
        }
        cout << res << endl;
    }
    return 0;
}