题意:
有\(n\)个怪物,每个怪物有攻击力\(a_i\)点;有\(m\)个英雄,每个英雄有攻击力\(p_i\)点,耐力\(s_{i}\)点。
怪物需要被依次杀死(按输入顺序)。
每一天可以挑选一个英雄去杀怪物,他可以杀死的怪物攻击力小于等于他本身(即\(a\leq p\)),每天最多可以杀死\(s\)个怪物。(每个英雄可以使用任意次)
问最少需要多少天可以杀死所有怪物(不能则输出\(-1\))。
分析:
\((1)\)我们找到怪物的最大攻击力和英雄的最大攻击力,判断是否要输出\(-1\)。
\((2)\)将英雄按攻击力\(p\)值排序,我们可以发现对于英雄\(b[i]\)而言,如果对于\(i<j\leq m\),且有\(b[i].s<b[j].s\),我们可以选择英雄\(j\),而不是英雄\(i\),那么我们可以把\(b[i].s\)替换为\(b[j].s\)(意思为选择英雄\(i\)时选择英雄\(j\))。
\((3)\)因此我们进行后缀操作将\(b[i].s\)改为英雄\(i\)~\(n\)中最大的耐力值,以便进行下一步。
\((4)\)对于某个怪物而言,我们可以找到一个英雄,他的攻击力刚好大于等于该怪物(二分)。我们上一步将该英雄的耐力改为了后缀最大值,那么我们便选择这个英雄。
\((5)\)我们从第一天开始,枚举每一个怪物,找到当前天我们可以杀死最多怪物的英雄,如果对于某个怪物而言,杀死他的人的耐力(我们进行了后缀操作)不足以支撑该天,我们将该怪物放到下一天,并重复操作,直至杀死所有怪物。因此我们需要保存的量有:当前的天数\(k\),昨天杀死的最后一只怪物的编号\(last\),今天所能杀死的最多怪物数(表现为所需要的最小耐力)\(minn\)。
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
using namespace std;
const int maxn = (ll) 2e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
struct node {
int p, s;
bool operator<(const node &b) {//用做排序
return p < b.p;
}
} b[maxn];
bool cmp(const node &x, int y) {//用做二分
return x.p < y;
}
int a[maxn];
int main() {
start;
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int maxa = 0, maxs = 0;//用做判-1
for (int i = 1; i <= n; ++i) {
cin >> a[i];
maxa = max(maxa, a[i]);
}
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
cin >> b[i].p >> b[i].s;
maxs = max(maxs, b[i].p);
}
if (maxa > maxs) {
cout << -1 << '\n';
continue;
}
sort(b + 1, b + m + 1);
for (int i = m - 1; i >= 1; --i)//后缀操作
b[i].s = max(b[i].s, b[i + 1].s);
int k = 1;
int last = 0;
int minn = inf;
for (int i = 1; i <= n; ++i) {
int t = lower_bound(b + 1, b + m + 1, a[i], cmp) - b;//刚好能杀死该怪物的英雄编号
minn = min(b[t].s, minn);//今天所需要的最小耐力
if (minn + last < i) {//将这只怪物放到明天杀
minn = b[t].s;
++k;
last = i - 1;
}
}
cout << k << '\n';
}
return 0;
}
本场比赛\(D\)和\(E\)惨痛教训:玩后缀一定要注意边界!!!
手机扫一扫
移动阅读更方便
你可能感兴趣的文章