D:Yet Another Monster Killing Problem

思路

1.首先对英雄的攻击里排序，如果攻击力一样就看耐力，再从后往前遍历，求出攻击力大于heros[i].p的所有英雄的最大耐力是多少，存入c[i]中

2.按顺序去遍历怪物，用一个mmax来存下消灭到当前怪物要达到的攻击力是多少，一个len来存要消灭的怪物的数量，其实就是要消灭的怪物中的最大攻击力是多少，然后用二分查找，找出第一个攻击力大于mmax的英雄，下标位idx，那么我们只要判断c[idx]是否比要消灭的怪物的数量len小，如果小，就表示前面一个怪物是能一次性消灭的最多的怪物的最后一个，那么ans++，并且mmax=mos[i]，表示重新开始一天，len=1，直到遍历完所有怪物。

3.如果最大怪物的攻击力大于最大英雄的攻击力，那么表示不能通关，输出-1

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <iostream>
using namespace std;
#define ll long long
int n, m;
const int N = 2e5+5;
struct hero {
	int p;
	int s;
	bool operator < (const hero& b)const {
		return p < b.p || ((p == b.p)&&s < b.s);
	}
}heros[N];
int mos[N];
int c[N];
int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		int tmax = 0;
		for (int i = 1; i <= n; i++) {
			scanf_s("%d", &mos[i]);
			tmax = max(tmax, mos[i]);
		}
		cin >> m;
		for (int i = 1; i <= m; i++) {
			scanf_s("%d%d", &heros[i].p, &heros[i].s);
		}
		int mmax = 0;
		int ans = 0;
		sort(heros + 1, heros + m + 1);
		for (int i = m; i >= 1; i--) {
			mmax = max(mmax, heros[i].s);
			c[i] = mmax;
		}
		if (heros[m].p < tmax) {
			ans = -1;
		}
		else {
			mmax = 0;
			int len = 0;
			for (int i = 1; i <= n; i++) {
				mmax = max(mos[i], mmax); len++;
				int l = 1, r = m;
				while (l < r) {
					int mid = (l + r) >> 1;
					if (heros[mid].p >= mmax) {
						r = mid;
					}
					else {
						l = mid + 1;
					}
				}
				if (c[l] < len) {
					ans++;
					mmax = mos[i];
					len = 1;				
				}
			}
			ans++;
		}
		cout << ans << "\n";
	}
	return 0;
}