Educational Codeforces Round 76 (Rated for Div. 2) - D. Yet Another Monster Killing Problem

Link: Yet Another Monster Killing Problem

Description:

You play a computer game. In this game, you lead a party of m heroes, and you have to clear a dungeon with n monsters. Each monster is characterized by its power ai. Each hero is characterized by his power pi and endurance si.

The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.

When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated k monsters, the hero fights with the monster k+1). When the hero fights the monster, there are two possible outcomes:

if the monster's power is strictly greater than the hero's power, the hero retreats from the dungeon. The current day ends;
otherwise, the monster is defeated.
After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the i-th hero cannot defeat more than si monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.

Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don't fight the monsters at all. Each hero can be used arbitrary number of times.

Input
The first line contains one integer t (1≤t≤1e5) — the number of test cases. Then the test cases follow.

The first line of each test case contains one integer n (1≤n≤2⋅1e5) — the number of monsters in the dungeon.

The second line contains n integers a1, a2, ..., an (1≤ai≤1e9), where ai is the power of the i-th monster.

The third line contains one integer m (1≤m≤2⋅1e5) — the number of heroes in your party.

Then m lines follow, each describing a hero. Each line contains two integers pi and si (1≤pi≤1e9, 1≤si≤n) — the power and the endurance of the i-th hero.

It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅1e5.

Output
For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or −1 if it is impossible).

Example
input
2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1
output
5
-1

Problem solving:
这道题的意思就是给你一堆怪物，然后给你几个战士。怪物和战士都有自己的攻击力，战士还会有一个耐力。只要战士的攻击力不小于怪物的攻击力，就可以把这个怪物杀死。每天只能派出一个战士，并且战士每杀一只怪物耐力减一。每个战士一天可以尽量多的杀怪物。问你最少需要几天可以把怪物杀完，如果杀不完就输出-1.注意：杀死怪物的顺序应该与输入的顺序一样，不能变

这里我补的代码里面主要思想是贪心。一共有n个怪物。那就把坚持i(1<=i<=n)天的战士的最大的攻击力存起来。然后从第一个怪物开始遍历，找到最多可以一天内杀死的怪物数，再从下一个怪物开始找，循环下去直到找完或者输出-1。具体可以看代码注释，个人认为写的还是很明白的。

Code:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie();
    int N, n, m;
    cin >> N;
    while (N--)
    {
        int         flag = 0, ans = 0;
        cin >> n;
        vector<int> a(n);
        vector<int> mx(n); //mx数组的含义很重要，它代表的是耐力为i的战士的最大攻击力
        for (int i = 0; i < n; i++)
            cin >> a[i];
        cin >> m;
        for (int i = 0, x, y; i < m; i++)
        {
            cin >> x >> y;
             mx[y - 1] = max(mx[y - 1], x);//这里我们下标从0开始。mx[i]代表的是可以坚持i天的战士的最大攻击力
        }
        for (int i = n - 2; i >= 0; i--)
            mx[i] = max(mx[i], mx[i + 1]);//这样处理是为了得到可以坚持至少i天的战士的最大攻击力，因为如果某个战士耐力大于i并且攻击力也更大，那么mx[i]的值就应该是他的攻击力。所以我们要从后往前推储存最大值
        for (int i = 0; i < n;)//从头开始杀怪物
        {
            int j = i, x = 0;
            while (j < n && mx[j - i ] >= max(x, a[j]))//这里mx的下标是j-i，要好好理解。这个while循环其实就是在找从第一只怪物开始吗，一天内最多杀死几只怪物
            {
                x = max(x, a[j]);
                j++;
            }//分别看当前一天内最多可以杀几只怪物，max(x,a[j])代表的就是这几天内怪物的最大攻击力，mx[j-i]代表的是战士的最大攻击力，如果战士的最大攻击力已经小于怪物了，说明连着打只能打j-i只怪物。然后跳出这个while循环
            if (j == i)
            {
                flag = 1; break;
            }//这是处理一下，j==i的情况只有一种情况会出现，即最大的战士攻击力小于这个怪物的攻击力，那么肯定杀不完
            ans++;//杀死这j-i只怪物用一天
            i = j;//从上一天杀死的最后一只怪物的下一只怪物开始下一次循环
        }
        if (flag)
            cout << "-1\n";
        else
            cout << ans << endl;
    }
}