#P3207. 数字序列比大小(200分)
-
1000ms
Tried: 172
Accepted: 31
Difficulty: 4
所属公司 :
华为od
数字序列比大小(200分)
题面描述
两个人 A 和 B 玩一个数字比大小的游戏。每个人各自有一个长度为 N 的数字序列,两个序列不相同且数字是随机的。每次对比时,A 和 B 各自从自己的序列中挑选一个数字进行比较,获胜者得 1 分,失败者扣 1 分,平局时分数不变。求 A 最大可能获得的分数。
思路
为了求出 A 在与 B 的数字比大小游戏中可能获得的最大分数,首先对两个数字序列进行排序,然后使用双指针策略,从两端比较 A 和 B 的最大和最小数字,选择最优的对抗策略:如果 A 的最大数字能胜过 B 的最大数字,则得分;若不敌,则用 A 的最小数字去消耗 B 的最大数字。通过这种方式逐步更新分数,最终计算出 A 的最大可能得分。
具体步骤
为了求出 A 能获得的最大分数,可以采用贪心算法的策略,具体步骤如下:
- 排序:首先将 A 和 B 的数字序列进行排序,便于后续的比较。
- 双指针策略:
- 定义四个指针:
leftA和rightA分别指向 A 序列中的最小和最大数字。leftB和rightB分别指向 B 序列中的最小和最大数字。
- 定义四个指针:
- 比分统计:
- 每次比较 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[leftA]>B[leftB],A 获胜,分数加 1,并将
- 如果 A[rightA]>B[rightB],A 获胜,分数加 1,并将
- 每次比较 A 的最大数字和 B 的最大数字:
通过上述策略,可以确保 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