英文题干

In the dream, May and Ray returned to the side of the little jellyfish. They continued to play their unique game just as they used to.

May and Ray are playing the roles of princesses of two countries, each with n knights. The i-th knight of May has a health value of , and the i-th knight of Ray has a health value of . The i-th knight of May stands opposite the i-th knight of Ray.

When a knight's health becomes 0, the knight dies. The game ends when no knights are standing opposite each other.

The two take turns commanding their knights to attack, with May commanding first. During each command, the current player can choose a pair of knights that are still standing opposite each other and order their knight to attack, reducing the opposing knight's health by 1.

May and Ray both care about their knights, so they both aim to maximize the number of their surviving knights. Both princesses are very clever and will always make the optimal decision.

You, the little jellyfish, as the witness of this duel, want to know in advance how many knights May will have surviving in the end.

Input:

This problem has multiple test cases. The first line contains a positive integer T representing the number of test cases.

For each test case, the first line contains a positive integer n representing the number of knights on each side.

The second line contains n positive integers representing the health values of May's knights.

The third line contains n positive integers representing the health values of Ray's knights.

Output:

For each test case, output a single positive integer representing the number of knights May will have surviving in the end.

中文题干

在梦中，梅和瑞回到了小水母的身边。他们继续像往常一样玩他们独特的游戏。

梅和瑞分别扮演两个国家的公主，每个公主各有 n() 名骑士。梅的第 i 名骑士的生命值为 ，瑞的第 i 名骑士的生命值为 。梅的第 i 名骑士正对瑞的第 i 名骑士。

当一名骑士的生命值变为 0 时，该骑士就会死亡。游戏在没有骑士互相对峙时结束。

两人轮流指挥他们的骑士进行攻击，梅先指挥。在每次指挥中，当前玩家可以选择一对仍然对峙的骑士，并命令他们的骑士攻击，令对方骑士的生命值减少 1。

梅和瑞都很关心他们的骑士，因此他们都希望最大化自己存活的骑士数量。两位公主都非常聪明，永远会做出最佳决策。

你作为这场决斗的见证者的小水母，想提前知道最后梅会有多少名骑士存活。

思路

简单的签到题，略（）

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

int a[maxn], b[maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];

        int cnt = 0, sur = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == b[i]) 
                cnt++;

            if (a[i] > b[i]) 
                sur++;
        }

        if (cnt & 1) 
            sur += cnt / 2 + 1;
        else 
            sur += cnt / 2;
        
        cout << sur << "\n";
    }
    return 0;
}