题面描述

两个人 $A$ 和 $B$ 玩一个数字比大小的游戏。每个人各自有一个长度为 $N$ 的数字序列，两个序列不相同且数字是随机的。每次对比时，$A$ 和 $B$ 各自从自己的序列中挑选一个数字进行比较，获胜者得 $1$ 分，失败者扣 $1$ 分，平局时分数不变。求 $A$ 最大可能获得的分数。

思路

为了求出 $A$ 在与 $B$ 的数字比大小游戏中可能获得的最大分数，首先对两个数字序列进行排序，然后使用双指针策略，从两端比较 $A$ 和 $B$ 的最大和最小数字，选择最优的对抗策略：如果 $A$ 的最大数字能胜过 $B$ 的最大数字，则得分；若不敌，则用 $A$ 的最小数字去消耗 $B$ 的最大数字。通过这种方式逐步更新分数，最终计算出 $A$ 的最大可能得分。

具体步骤

为了求出 $A$ 能获得的最大分数，可以采用贪心算法的策略，具体步骤如下：

1. 排序：首先将 $A$ 和 $B$ 的数字序列进行排序，便于后续的比较。
2. 双指针策略：
   • 定义四个指针：
     • leftA 和 rightA 分别指向 $A$ 序列中的最小和最大数字。
     • leftB 和 rightB 分别指向 $B$ 序列中的最小和最大数字。
3. 比分统计：
   • 每次比较 $A$ 的最大数字和 $B$ 的最大数字：
     • 如果 $A[rightA] > B[rightB]$，$A$ 获胜，分数加 $1$，并将 rightA 和 rightB 各自左移一位。
     • 如果 $A[rightA] < B[rightB]$，$A$ 失利，分数减 $1$，$A$ 使用最小的数字 leftA 去对抗 $B$ 的最大数字 rightB，然后将 leftA 右移，rightB 左移。
     • 如果 $A[rightA] == B[rightB]$，则比较 $A$ 的最小数字与 $B$ 的最小数字：
       • 如果 $A[leftA] > B[leftB]$，$A$ 获胜，分数加 $1$，并将 leftA 和 leftB 各自右移一位。
       • 否则，$A$ 选择使用最小的数字 leftA 去对抗 $B$ 的最大数字 rightB，如果 $B[rightB] > A[leftA]$，则分数减 $1$，然后将 leftA 右移，rightB 左移。

通过上述策略，可以确保 $A$ 在每一步都做出最优选择，最大化最终的得分。

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n); // 数列A
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> b(n); // 数列B
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    // 对两个序列进行排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int leftA = 0; // 指向A最慢的数字
    int rightA = n - 1; // 指向A最快的数字

    int leftB = 0; // 指向B最慢的数字
    int rightB = n - 1; // 指向B最快的数字

    int score = 0; // 记录A获得的分数

    while (leftA <= rightA) {
        if (a[rightA] > b[rightB]) {
            // A最快的数字胜过B最快的数字
            score += 1;
            rightA--; // A使用最快的数字
            rightB--; // B失去最快的数字
        } else if (a[rightA] < b[rightB]) {
            // A最快的数字输给B最快的数字
            score -= 1;
            leftA++; // A使用最慢的数字
            rightB--; // B失去最快的数字
        } else {
            // A和B的最快数字平局
            if (a[leftA] > b[leftB]) {
                // 如果A最慢的数字胜过B最慢的数字
                score += 1;
                leftA++;
                leftB++;
            } else {
                // 如果A最慢的数字不敌B最慢的数字
                // A的最慢数字消耗掉B的最快数字
                if (b[rightB] > a[leftA]) {
                    score -= 1; // A失去分数
                }
                leftA++;
                rightB--; // B失去最快的数字
            }
        }
    }

    cout << score; // 输出最终得分

    return 0;
}

python

def max_score(a, b):
    # 排序
    a.sort()
    b.sort()

    leftA = 0  # 指向A最慢的数字
    rightA = len(a) - 1  # 指向A最快的数字

    leftB = 0  # 指向B最慢的数字
    rightB = len(b) - 1  # 指向B最快的数字

    score = 0  # 记录A获得的分数

    while leftA <= rightA:
        if a[rightA] > b[rightB]:
            # A最快的数字胜过B最快的数字
            score += 1
            rightA -= 1  # A使用最快的数字
            rightB -= 1  # B失去最快的数字
        elif a[rightA] < b[rightB]:
            # A最快的数字输给B最快的数字
            score -= 1
            leftA += 1  # A使用最慢的数字
            rightB -= 1  # B失去最快的数字
        else:
            # A和B的最快数字平局
            if a[leftA] > b[leftB]:
                # 如果A最慢的数字胜过B最慢的数字
                score += 1
                leftA += 1
                leftB += 1
            else:
                # 如果A最慢的数字不敌B最慢的数字
                if b[rightB] > a[leftA]:
                    score -= 1  # A失去分数
                leftA += 1
                rightB -= 1  # B失去最快的数字

    return score

# 主函数
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(max_score(a, b))

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n]; // 数列A
        int[] b = new int[n]; // 数列B

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }

        // 对两个序列进行排序
        Arrays.sort(a);
        Arrays.sort(b);

        int leftA = 0; // 指向A最慢的数字
        int rightA = n - 1; // 指向A最快的数字

        int leftB = 0; // 指向B最慢的数字
        int rightB = n - 1; // 指向B最快的数字

        int score = 0; // 记录A获得的分数

        while (leftA <= rightA) {
            if (a[rightA] > b[rightB]) {
                // A最快的数字胜过B最快的数字
                score += 1;
                rightA--; // A使用最快的数字
                rightB--; // B失去最快的数字
            } else if (a[rightA] < b[rightB]) {
                // A最快的数字输给B最快的数字
                score -= 1;
                leftA++; // A使用最慢的数字
                rightB--; // B失去最快的数字
            } else {
                // A和B的最快数字平局
                if (a[leftA] > b[leftB]) {
                    // 如果A最慢的数字胜过B最慢的数字
                    score += 1;
                    leftA++;
                    leftB++;
                } else {
                    // 如果A最慢的数字不敌B最慢的数字
                    if (b[rightB] > a[leftA]) {
                        score -= 1; // A失去分数
                    }
                    leftA++;
                    rightB--; // B失去最快的数字
                }
            }
        }

        System.out.println(score); // 输出最终得分
    }
}

题目内容

$A，B$ 两个人玩一个数字比大小的游戏，在游戏前，两个人会拿到相同长度的两个数字序列，两个数字序列不相同的，且其中的数字是随机的。

$A，B$ 各自从数字序列中挑选出一个数字进行大小比较，赢的人得 $1$ 分，输的人扣 $1$ 分，相等则各自的分数不变。

用过的数字需要丢弃。

求 $A$ 可能赢 $B$ 的最大分数。

输入描述

输入数据的第 $1$ 个数字表示数字序列的长度 $N$ ，后面紧跟着两个长度为 $N$ 的数字序列。

输出描述

$A$ 可能赢 $B$ 的最大分数

样例1

输入

3
4 8 10
3 6 4

输出

3

说明

输入数据第 $1$ 个数字表示数字序列长度为 $3$ ，后面紧跟着两个长度为 $3$ 的数字序列。

序列 $A$ ：$4$ $8$ $10$

序列 $B$ ：$3$ $6$ $4$

$A$ 可以赢的最大分数是 $3$ 。获得该分数的比大小过程可以是：

$1$）$A$ ：$4$ $B$ ：$3$

$2$）$A$：$8$ $B$：$6$

$3$）$A$：$10$ B：$4$