比賽的時(shí)候想著貪心寫，一直WA。賽后補(bǔ)題補(bǔ)了兩天，總算是有點(diǎn)頭緒了

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:
這道題的意思就是給你一堆怪物，然后給你幾個(gè)戰(zhàn)士。怪物和戰(zhàn)士都有自己的攻擊力，戰(zhàn)士還會(huì)有一個(gè)耐力。只要戰(zhàn)士的攻擊力不小于怪物的攻擊力，就可以把這個(gè)怪物殺死。每天只能派出一個(gè)戰(zhàn)士，并且戰(zhàn)士每殺一只怪物耐力減一。每個(gè)戰(zhàn)士一天可以盡量多的殺怪物。問你最少需要幾天可以把怪物殺完，如果殺不完就輸出-1.注意：殺死怪物的順序應(yīng)該與輸入的順序一樣，不能變

這里我補(bǔ)的代碼里面主要思想是貪心。一共有n個(gè)怪物。那就把堅(jiān)持i(1<=i<=n)天的戰(zhàn)士的最大的攻擊力存起來。然后從第一個(gè)怪物開始遍歷，找到最多可以一天內(nèi)殺死的怪物數(shù)，再從下一個(gè)怪物開始找，循環(huán)下去直到找完或者輸出-1。具體可以看代碼注釋，個(gè)人認(rèn)為寫的還是很明白的。

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數(shù)組的含義很重要，它代表的是耐力為i的戰(zhàn)士的最大攻擊力
        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);//這里我們下標(biāo)從0開始。mx[i]代表的是可以堅(jiān)持i天的戰(zhàn)士的最大攻擊力
        }
        for (int i = n - 2; i >= 0; i--)
            mx[i] = max(mx[i], mx[i + 1]);//這樣處理是為了得到可以堅(jiān)持至少i天的戰(zhàn)士的最大攻擊力，因?yàn)槿绻硞€(gè)戰(zhàn)士耐力大于i并且攻擊力也更大，那么mx[i]的值就應(yīng)該是他的攻擊力。所以我們要從后往前推儲(chǔ)存最大值
        for (int i = 0; i < n;)//從頭開始?xì)⒐治?        {
            int j = i, x = 0;
            while (j < n && mx[j - i ] >= max(x, a[j]))//這里mx的下標(biāo)是j-i，要好好理解。這個(gè)while循環(huán)其實(shí)就是在找從第一只怪物開始嗎，一天內(nèi)最多殺死幾只怪物
            {
                x = max(x, a[j]);
                j++;
            }//分別看當(dāng)前一天內(nèi)最多可以殺幾只怪物，max(x,a[j])代表的就是這幾天內(nèi)怪物的最大攻擊力，mx[j-i]代表的是戰(zhàn)士的最大攻擊力，如果戰(zhàn)士的最大攻擊力已經(jīng)小于怪物了，說明連著打只能打j-i只怪物。然后跳出這個(gè)while循環(huán)
            if (j == i)
            {
                flag = 1; break;
            }//這是處理一下，j==i的情況只有一種情況會(huì)出現(xiàn)，即最大的戰(zhàn)士攻擊力小于這個(gè)怪物的攻擊力，那么肯定殺不完
            ans++;//殺死這j-i只怪物用一天
            i = j;//從上一天殺死的最后一只怪物的下一只怪物開始下一次循環(huán)
        }
        if (flag)
            cout << "-1\n";
        else
            cout << ans << endl;
    }
}