专栏文章

题解：CF1257D Yet Another Monster Killing Problem

hhhhua
CF1257D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8ciav
此快照首次捕获于
2025/12/03 07:49
3 个月前
此快照最后确认于
2025/12/03 07:49
3 个月前
查看原文
很容易注意到一天要打最多的怪。
接着考虑在一天中当前打到第 ll 个怪（未打），将打掉到第 rr 个怪，可行否？
  • 对怪物， 若存在英雄 ii，使得 si≥r−l+1s_i \geq r-l+1 且 pi≥max⁡i=l..raip_i \geq \max_{i=l..r}{a_i}，则可行。（充要）
到这里其实可以做了呢，我们把英雄按 ss 排个序，我们二分这个 rr，那相当于在一个后缀里面查 pip_i 最大值。
  • 要得到 O(n)O(n) 算法，我们还得动点脑子。
既然可以二分答案，那能不能增量式？因为查询不依赖 l、rl、r，那其实这个过程是非常重复的，那我们可以预处理出 bstr=max⁡si=r..npibst_r = \max_{s_i=r..n} p_i，对每天从 ll 开始循环到可行条件不成立即可。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...