当前位置：首页 > news >正文

华为OD 机试 2025-数字序列比大小

news 2025/7/2 11:23:26

题目描述

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

输入描述
输入数据的第一个数字表示数字序列的长度 N，后面紧跟着两个长度为 N 的数字序列。
输出描述
输出 A 可能赢 B 的最大分数。
补充说明
1. 假设 A 知道 B 的数字序列，且总是 B 先挑选数字并明示。
2. 采用贪心策略：能赢的一定要赢，要输的尽量减少损失。
示例
```
输入：
3
4 8 10
3 6 4输出：
3
```
过程示例：
- A:4 vs B:3 → +1
- A:8 vs B:6 → +1
- A:10 vs B:4 → +1

优化思路解析

双端指针贪心
- 对 A、B 两个序列分别从小到大排序。
- 用两个指针 bL、bR 分别指向 B 的最小端和最大端。
- 遍历 A 中按升序排列的每个元素 a：
  - 若 a > B[bL]，则对战 B 的最小值，必赢，得 +1 分，bL++。
  - 否则，用 a 对战 B 的最大值：
    - 若 a < B[bR]，必输，得 –1 分；
    - 否则（相等）平局，得分不变。
  - 操作后，bR--。
正确性
- 任何能赢的局面都拿下；
- 无法赢时，用最“小”的代价牺牲最“强”的对手卡，减少后续影响。
时间复杂度
- 排序 O(N log N)，遍历 O(N)，总体 O(N log N)，可处理 N ≈ 10⁵。

Python 实现

def max_score(A, B):A.sort()B.sort()bL, bR = 0, len(B) - 1score = 0for a in A:if a > B[bL]:score += 1bL += 1else:if a < B[bR]:score -= 1bR -= 1return scoreif __name__ == "__main__":import sysdata = list(map(int, sys.stdin.read().split()))N = data[0]A = data[1:1+N]B = data[1+N:1+2*N]print(max_score(A, B))

Java 实现

import java.util.*;public class Main {public static int maxScore(int[] A, int[] B) {Arrays.sort(A);Arrays.sort(B);int bL = 0, bR = B.length - 1, score = 0;for (int a : A) {if (a > B[bL]) {score++;bL++;} else {if (a < B[bR]) {score--;}bR--;}}return score;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] A = new int[N], B = new int[N];for (int i = 0; i < N; i++) {A[i] = sc.nextInt();}for (int i = 0; i < N; i++) {B[i] = sc.nextInt();}System.out.println(maxScore(A, B));sc.close();}
}

JavaScript 实现

function maxScore(A, B) {A.sort((a, b) => a - b);B.sort((a, b) => a - b);let bL = 0, bR = B.length - 1, score = 0;for (const a of A) {if (a > B[bL]) {score++;bL++;} else {if (a < B[bR]) {score--;}bR--;}}return score;
}// Node.js 读取输入并运行
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const nums = [];
rl.on('line', line => {nums.push(...line.trim().split(/\s+/).map(Number));if (nums.length >= nums[0] * 2 + 1) {const N = nums[0];const A = nums.slice(1, 1 + N);const B = nums.slice(1 + N, 1 + 2 * N);console.log(maxScore(A, B));rl.close();}
});