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

题目描述

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

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

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

输入描述

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

输出描述

A可能赢B的最大分数

备注

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

用例

题目解析

本题其实就是田忌赛马问题，解析可以参考我的这篇博客：

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("%dn", 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);
}