Dear problem setter, I downloaded Hearthstone. Why is my Threads of Despair a three-cost card?

—Pan-fried-chicken

Problem Statement

Fried-chicken is a devoted player of Hearthstone. Since the game resumed operations in the Chinese mainland, he has been obsessed with it and reached Silver 2 rank in Standard mode. Today, while ranking up using Death Knight, he encountered a formidable opponent, Stewed-chicken, and was left with just $1$ Health. To survive, Fried-chicken must eliminate all of Stewed-chicken’s minions. Fortunately, he can use spell cards and his minions’ attacks to achieve this goal.

Specifically, this game involves two factions: Fried-chicken and Stewed-chicken. Each faction has some minions. The $i$-th minion has $h_i$ Health. It is now Fried-chicken’s turn, and each of his minions can attack any one minion from the opposing faction at most once. When one minion attacks another, both minions lose $1$ Health. If a minion’s Health is reduced to $0$ or less, it dies and can no longer attack or be attacked.

To achieve his goal, Fried-chicken casts the spell “Threads of Despair,” causing every minion to explode upon death, which reduces the Health of all minions by $1$. If the explosion causes the death of other minions, other minions will also explode immediately. Fried-chicken cannot have his minions attack other minions until all explosion effects have finished. After casting the spell, Fried-chicken can make his minions attack Stewed-chicken’s minions in any order he chooses. He wants to know if there exists an attack order that allows Fried-chicken to eliminate all of Stewed-chicken’s minions.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \leq T \leq 5 \times 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 5 \times 10^5$), representing the number of Fried-chicken’s minions and Stewed-chicken’s minions, respectively.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \leq h_i \leq 10^9$), where $h_i$ represents the Health of Fried-chicken’s $i$-th minion.

The third line contains $m$ integers $h’_1, h’_2, \dots, h’_m$ ($1 \leq h’_i \leq 10^9$), where $h’_i$ represents the Health of Stewed-chicken’s $i$-th minion.

For each test file, it is guaranteed that the sum of all $n$ across all test cases does not exceed $5 \times 10^5$, and the sum of all $m$ across all test cases does not exceed $5 \times 10^5$.

Output

For each test case, output “Yes” if Fried-chicken can eliminate all of Stewed-chicken’s minions; otherwise, output “No”.

You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void solve()
{         
    int n,m;
    cin >> n >> m;
    vector<int> a(n+1),b(m+1);
    int lazy = 0;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        if(a[i] == 1) lazy++;
        a[i]--; //先默认所有士兵已经进行完了进攻操作，为后续安排进攻顺序提供便利
    }
    int valid = n - lazy; // 初始生命不为1的士兵，每人均可提供一次攻打机会
    if(lazy >= 1) valid++; // 若存在初始生命就为1的士兵，他们一个整体的攻击次数为1
    for(int i=1;i<=m;i++) cin >> b[i];
    sort(a.begin()+1,a.end());
    sort(b.begin()+1,b.end());
    int ptr = 1; // 初始化指针，先让其移动到可以进行操作的士兵前
    while(a[ptr] == 0 and ptr <= n) ptr++; // 使指针指向所有轮次结束后我方第一个没有爆炸的士兵位置
    while(a[ptr] <= lazy and ptr <= n) ptr++,lazy++; // 使指针指向我方第一个没有被先前爆炸余波影响的士兵位置
    for(int i=1;i<=m;i++) 
    {
        if(b[i] <= lazy) lazy++; // 如果此名敌方士兵已经被爆炸余波影响则爆炸影响继续++
        else // 否则看此名地方士兵需要至少消耗攻打的士兵数量是否足够
        {
            if(b[i] - lazy > valid) // 不足则代表无法击败
            {
                cout << "No\n";
                return;
            }
            valid -= (b[i] - lazy); // 否则减去需用士兵数量
            lazy++; // 此名士兵成功攻打，余波影响++
        }
        while(a[ptr] <= lazy and ptr <= n) lazy++,ptr++; // 最后再查我方士兵还能不能再爆炸
    }
    cout << "Yes\n";

}