跳至主要內容

2025A-数字序列比大小

题目描述与示例

题目描述

A，B两个人玩一个数字比大小的游戏，在游戏前，两个人会拿到相同长度的两个数字序列，两个数字序列不相同的，且其中的数字是随机的。 A，B各自从数字序列中挑选出一个数字进行大小比较，赢的人得1分，输的人扣1分，相等则各自的分数不变。 用过的数字需要丢弃。 求A可能赢B的最大分数。

输入描述

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

输出描述

A可能赢B的最大分数

示例

输入

3
4 8 10
3 6 4

输出

3

解题思路

这道题很明显是一道贪心的题目。由于平局情况的出现，本题难点在于我们如何地选择策略。

首先需要将两个数组各自排序，方便考虑。我们设置四个指针ia_left，ia_right，ib_left，ib_right，分别指向A、B数组中尚未比较过的元素的最小值和最大值。其初始化为

ia_left = 0
ib_left = 0
ia_right = n-1
ib_right = n-1

在一个while循环中，比较A和B中尚未比较过元素的最小值，即A[ia_left]和B[ib_left]。若

  • A[ia_left] > B[ib_left]。由于选择B中的其他数字，可能会导致A[ia_left]无法获胜，故选择该组进行比较，A获胜。

    • if A[ia_left] > B[ib_left]:
    ans += 1
    ia_left += 1
    ib_left += 1

  • A[ia_left] < B[ib_left]。由于此时A中最小值小于B中的任意一个元素，我们不妨采取田忌赛马的策略，让A[ia_left]和B[ib_right]进行分组，B获胜。

if A[ia_left] < B[ib_left]:
    ans -= 1
    ia_left += 1
    ib_right -= 1

  • A[ia_left] == B[ib_left]。这是最复杂的情况，我们需要再嵌套一个while循环，以考虑A和B中尚未比较过元素的最大值，即A[ia_right]和B[ib_right]情况。若

    • A[ia_right] > B[ib_right]，即以下情况

      • 若此时令A[ia_left]和B[ib_right]分组，由于A[ia_right]无论怎么配对都是必胜，但A[ia_left]原本可以平局的配对现在却输了，故不能采取这样的策略。

      • 故让A[ia_right]和B[ib_right]分组，A[ia_right]获胜。

      • 由于A[ia_left] == B[ib_left]的情况仍然存在，故此时内层的while循环不能退出。

      • if A[ia_right] > B[ib_right]:
    ans += 1
    ia_right -= 1
    ib_right -= 1

    • A[ia_right] < B[ib_right]，即以下情况

      • 由于此时B[ib_right]大于A中的任何一个元素，A无论如何配对都必输，故仍然维持着田忌赛马的策略令A[ia_left]和B[ib_right]分组，获胜。
      • 由于此时ia_left前进，故内层while循环可以退出。

    • A[ia_right] == B[ib_right]，即以下情况

      • 此时固然可以令A[ia_left]和B[ib_left]、A[ai_right]和B[ib_right]两两分组，但剩余元素的比较可能会让A的失利场次增多。

      • 故仍然应该选择A[ia_left]和B[ib_right]进行分组，此时丢失的分数，可能能够在A[ia_right]的其他配对中获取回来。

      • 由于此时ia_left前进，故内层while循环可以退出。

      • 显然这种情况可以和上一种情况A[ia_right] < B[ib_right]合并在一起，即

        • if A[ia_right] <= B[ib_right]:
    if A[ia_left] < B[ib_right]:
        ans -= 1
    ia_left += 1
    ib_right -= 1
    break

      • 要注意有可能出现 A[ia_left] == A[ia_right] == B[ib_left] == B[ib_right]的情况，故需要多加一句特殊判断。

本题核心逻辑其实就是田忌赛马，在A[ia_left]必定无法胜利的情况下（无论是必输还是可能平局），都尽量地让A[ia_left]和B[ib_right]配对。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 分别对A和B数组进行排序
A.sort()
B.sort()
# 设置四个指针
ia_left = 0
ib_left = 0
ia_right = n-1
ib_right = n-1
ans = 0

# 进行循环，
# 由于每次判断，A和B中的指针必定均移动一位
# 故此处只需设置一个退出循环条件即可

while ia_left < ia_right:
    # A中最小值【大于】B中最小值的情况
    if A[ia_left] > B[ib_left]:
        ans += 1
        ia_left += 1
        ib_left += 1

    # A中最小值【小于】B中最小值的情况
    elif A[ia_left] < B[ib_left]:
        ans -= 1
        ia_left += 1
        ib_right -= 1

    # A中最小值【等于】B中最小值的情况
    else:
        # 内层while循环
        while ia_left < ia_right:
            # A中最大值【大于】B中最大值的情况
            if A[ia_right] > B[ib_right]:
                ans += 1
                ia_right -= 1
                ib_right -= 1
            # A中最大值【小于等于】B中最大值的情况
            else:
                if A[ia_right] <= B[ib_right]:
                    if A[ia_left] < B[ib_right]:
                        ans -= 1
                    ia_left += 1
                    ib_right -= 1
                    break

# 退出循环时，存在ia_left == ia_right，ib_left == ib_right
# 故需要再重新判断最后一组数组A[ia_left]和B[ib_left]
if A[ia_left] > B[ib_left]:
    ans += 1
elif A[ia_left] < B[ib_left]:
    ans -= 1

print(ans)

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];
        int[] B = new int[n];

        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 iaLeft = 0;
        int ibLeft = 0;
        int iaRight = n - 1;
        int ibRight = n - 1;
        int ans = 0;

        while (iaLeft < iaRight) {
            if (A[iaLeft] > B[ibLeft]) {
                ans++;
                iaLeft++;
                ibLeft++;
            } else if (A[iaLeft] < B[ibLeft]) {
                ans--;
                iaLeft++;
                ibRight--;
            } else {
                while (iaLeft < iaRight) {
                    if (A[iaRight] > B[ibRight]) {
                        ans++;
                        iaRight--;
                        ibRight--;
                    } else {
                        if (A[iaRight] <= B[ibRight]) {
                            if (A[iaLeft] < B[ibRight]) {
                                ans--;
                            }
                            iaLeft++;
                            ibRight--;
                            break;
                        }
                    }
                }
            }
        }

        if (A[iaLeft] > B[ibLeft]) {
            ans++;
        } else if (A[iaLeft] < B[ibLeft]) {
            ans--;
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    vector<int> B(n);

    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> B[i];
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int iaLeft = 0;
    int ibLeft = 0;
    int iaRight = n - 1;
    int ibRight = n - 1;
    int ans = 0;

    while (iaLeft < iaRight) {
        if (A[iaLeft] > B[ibLeft]) {
            ans++;
            iaLeft++;
            ibLeft++;
        } else if (A[iaLeft] < B[ibLeft]) {
            ans--;
            iaLeft++;
            ibRight--;
        } else {
            while (iaLeft < iaRight) {
                if (A[iaRight] > B[ibRight]) {
                    ans++;
                    iaRight--;
                    ibRight--;
                } else {
                    if (A[iaRight] <= B[ibRight]) {
                        if (A[iaLeft] < B[ibRight]) {
                            ans--;
                        }
                        iaLeft++;
                        ibRight--;
                        break;
                    }
                }
            }
        }
    }

    if (A[iaLeft] > B[ibLeft]) {
        ans++;
    } else if (A[iaLeft] < B[ibLeft]) {
        ans--;
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(NlogN)。排序所需的时间复杂度。在while循环中，两个列表中的每个元素只会经过一次。

空间复杂度：O(1)。仅需四个指针，若干常数变量

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法