(新卷,200分)- 数字序列比大小（Java JS Python C）-平芜编程栈

(新卷,200分)- 数字序列比大小（Java & JS & Python & C）

题目描述

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

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

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

输入描述

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

输出描述

A可能赢B的最大分数

备注

这里要求计算A可能赢B的最大分数，不妨假设，A知道B的数字序列，且总是B先挑选数字并明示。
可以采用贪心策略，能赢的一定要赢，要输的尽量减少损失。

用例

输入

3
4 8 10
3 6 4

输出

说明

输入数据第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

题目解析

本题其实就是田忌赛马问题

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length == 3) { const n = parseInt(lines[0]); const a = lines[1].split(" ").map(Number); const b = lines[2].split(" ").map(Number); console.log(getResult(n, a, b)); lines.length = 0; } }); function getResult(n, a, b) { a.sort((a, b) => a - b); b.sort((a, b) => a - b); let la = 0; // 指向田忌最慢的马 let ra = n - 1; // 指向田忌最快的马 let lb = 0; // 指向齐王最慢的马 let rb = n - 1; // 指向齐王最快的马 let ans = 0; // 记录田忌获得银币数 while (la <= ra) { if (a[ra] > b[rb]) { // 田忌最快的马 比 齐王最快的马要快, 则直接比 ans += 1; ra--; rb--; } else if (a[ra] < b[rb]) { // 田忌最快的马 比 齐王最快的马要慢, 则结果肯定输, 为了保留田忌最快的马, 我们应该用田忌最慢的马去消耗掉齐王最快的马 ans -= 1; la++; rb--; } else { // 田忌最快的马 和 齐王最快的 速度相同, 此时如果平局的话，则会让田忌损失最快的马，因此我们应该找到田忌最慢的马, 即田忌必输的马来消耗掉齐王最快的马 if (a[la] > b[lb]) { // 如果田忌最慢的马 比 齐王最慢的马 快, 则此时田忌最慢的马不是必输的马 ans += 1; la++; lb++; } else { // 如果田忌最慢的马速度 <= 齐王最慢的马速度, 此时应该让田忌最慢的马 去消耗 齐王最快的马 // 如果齐王最快的马速度 > 田忌最慢的马速度，则田忌失去银币 // 如果齐王最快的马速度 == 田忌最慢的马速度，则田忌不失去银币 if (b[rb] > a[la]) ans -= 1; la++; rb--; } } } return ans; }

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); int[] a = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int[] b = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); System.out.println(getResult(n, a, b)); } public static int getResult(int n, int[] a, int[] b) { Arrays.sort(a); Arrays.sort(b); int la = 0; // 指向田忌最慢的马 int ra = n - 1; // 指向田忌最快的马 int lb = 0; // 指向齐王最慢的马 int rb = n - 1; // 指向齐王最快的马 int ans = 0; // 记录田忌获得银币数 while (la <= ra) { if (a[ra] > b[rb]) { // 田忌最快的马 比 齐王最快的马要快, 则直接比 ans += 1; ra--; rb--; } else if (a[ra] < b[rb]) { // 田忌最快的马 比 齐王最快的马要慢, 则结果肯定输, 为了保留田忌最快的马, 我们应该用田忌最慢的马去消耗掉齐王最快的马 ans -= 1; la++; rb--; } else { // 田忌最快的马 和 齐王最快的 速度相同, 此时如果平局的话，则会让田忌损失最快的马，因此我们应该找到田忌最慢的马, 即田忌必输的马来消耗掉齐王最快的马 if (a[la] > b[lb]) { // 如果田忌最慢的马 比 齐王最慢的马 快, 则此时田忌最慢的马不是必输的马 ans += 1; la++; lb++; } else { // 如果田忌最慢的马速度 <= 齐王最慢的马速度, 此时应该让田忌最慢的马 去消耗 齐王最快的马 // 如果齐王最快的马速度 > 田忌最慢的马速度，则田忌失去银币 // 如果齐王最快的马速度 == 田忌最慢的马速度，则田忌不失去银币 if (b[rb] > a[la]) ans -= 1; la++; rb--; } } } return ans; } }

Python算法源码

# 输入获取 n = int(input()) a = list(map(int, input().split())) # 田忌的马速度数组 b = list(map(int, input().split())) # 齐王的马速度数组 # 算法入口 def getResult(): a.sort() b.sort() la = 0 # 指向田忌最慢的马 ra = n - 1 # 指向田忌最快的马 lb = 0 # 指向齐王最慢的马 rb = n - 1 # 指向齐王最快的马 ans = 0 # 记录田忌获得银币数 while la <= ra: if a[ra] > b[rb]: # 田忌最快的马 比 齐王最快的马要快, 则直接比 ans += 1 ra -= 1 rb -= 1 elif a[ra] < b[rb]: # 田忌最快的马 比 齐王最快的马要慢, 则结果肯定输, 为了保留田忌最快的马, 我们应该用田忌最慢的马去消耗掉齐王最快的马 ans -= 1 la += 1 rb -= 1 else: # 田忌最快的马 和 齐王最快的 速度相同, 此时如果平局的话，则会让田忌损失最快的马，因此我们应该找到田忌最慢的马, 即田忌必输的马来消耗掉齐王最快的马 if a[la] > b[lb]: # 如果田忌最慢的马 比 齐王最慢的马 快, 则此时田忌最慢的马不是必输的马 ans += 1 la += 1 lb += 1 else: # 如果田忌最慢的马速度 <= 齐王最慢的马速度, 此时应该让田忌最慢的马 去消耗 齐王最快的马 # 如果齐王最快的马速度 > 田忌最慢的马速度，则田忌失去银币 # 如果齐王最快的马速度 == 田忌最慢的马速度，则田忌不失去银币 if b[rb] > a[la]: ans -= 1 la += 1 rb -= 1 return ans # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 int getResult(int n, int* a, int* b); int cmp(const void* a, const void* b); int main() { int n; scanf("%d", &n); int a[MAX_SIZE]; for(int i=0; i<n; i++) { scanf("%d", &a[i]); } int b[MAX_SIZE]; for(int i=0; i<n; i++) { scanf("%d", &b[i]); } printf("%d\n", getResult(n, a, b)); return 0; } int getResult(int n, int* a, int* b) { qsort(a, n, sizeof(int), cmp); qsort(b, n, sizeof(int), cmp); int la = 0; // 指向田忌最慢的马 int ra = n - 1; // 指向田忌最快的马 int lb = 0; // 指向齐王最慢的马 int rb = n - 1; // 指向齐王最快的马 int ans = 0; // 记录田忌获得银币数 while(la <= ra) { if(a[ra] > b[rb]) { // 田忌最快的马 比 齐王最快的马要快, 则直接比 ans += 1; ra--; rb--; } else if(a[ra] < b[rb]) { // 田忌最快的马 比 齐王最快的马要慢, 则结果肯定输, 为了保留田忌最快的马, 我们应该用田忌最慢的马去消耗掉齐王最快的马 ans -= 1; la++; rb--; } else { // 田忌最快的马 和 齐王最快的 速度相同, 此时如果平局的话，则会让田忌损失最快的马，因此我们应该找到田忌最慢的马, 即田忌必输的马来消耗掉齐王最快的马 if(a[la] > b[lb]) { // 如果田忌最慢的马 比 齐王最慢的马 快, 则此时田忌最慢的马不是必输的马 ans += 1; la++; lb++; } else { // 如果田忌最慢的马速度 <= 齐王最慢的马速度, 此时应该让田忌最慢的马 去消耗 齐王最快的马 // 如果齐王最快的马速度 > 田忌最慢的马速度，则田忌失去银币 // 如果齐王最快的马速度 == 田忌最慢的马速度，则田忌不失去银币 if(b[rb] > a[la]) { ans -= 1; } la++; rb--; } } } return ans; } int cmp(const void* a, const void* b) { return *((int*) a) - *((int*) b); }