上海计算机学会2022年10月月赛C++乙组T3田忌赛马
发布时间
阅读量：
阅读量
田忌赛马
内存限制: 256 Mb时间限制: 1000 ms
题目描述
田忌和齐王各有 n 匹马，田忌的马速度分别为 a1,a2,…,an，而齐王的马速度分别为 b1,b2,…,bn。
田忌与齐王比赛 n 轮，双方每轮挑出一匹新马，若田忌的马更快，田忌加一分，若齐王的马更快，齐王加一分，若双方速度一样，分数不变。
齐王永远按照固定的顺序选择马匹参赛，田忌应该采取什么策略才能让自己的得分减齐王的得分变得最大？
输入格式
第一行：单个整数 n
第二行：n 个整数 a1,a2,…,an
第三行：n 个整数 b1,b2,…,bn
输出格式
单个整数：表示田忌得分减齐王得分的最大值
数据范围
- 对于 30% 的数据，n≤20
- 对于 60% 的数据，n≤2000
- 对于 100% 的数据，n≤200,000
- 1≤ai,bi≤1,000,000
样例数据
输入:
3
10 20 30
15 25 35
输出:
1
解析：贪心算法
我们先对田忌的马和齐王的马进行排序，
然后我们来考虑以下几种情况：
1.当田忌最慢的马比齐王最慢的马快，赢一场。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。
2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。
3.当田忌最慢的和齐王最慢的马慢相等时，分4，5，6讨论。
4.当田忌最快的马比齐王最快的马快时，赢一场先。因为最快的马的用途就是来赢别人快的马，别人慢的马什么马都能赢。
5.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场，因为反正要输一场，不如拿最没用的马输。
6.当田忌最快的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比。因为最差的结果也是平局。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
int pa1 = 1;//田忌的慢马
int pa2 = n;//田忌的快马
int pb1 = 1;//齐王的慢马
int pb2 = n;//齐王的快马
int qw = 0;//齐王胜利次数
int tj = 0;//田忌胜利次数
while (pa1 <= pa2) {//只要还有马
if (a[pa1] > b[pb1]) {//田忌最慢的马比齐王最慢的马快，赢他
pa1++;
pb1++;
tj++;
} else if (a[pa1] < b[pb1]) {//田忌最慢的马比齐王最慢的马慢，消耗齐王最快的马
pa1++;
pb2--;
qw++;
} else if (a[pa1] == b[pb1]) {//如果最慢的马一样快
if (a[pa2] > b[pb2]) {//田忌最快的马比齐王最快的马快，赢他
pa2--;
pb2--;
tj++;
} else if (a[pa2] < b[pb2]) {//田忌最快的马比齐王最快的马慢，用最慢的马消耗齐王最快的马
pb2--;
pa1++;
qw++;
} else if (a[pa2] == b[pb2]) {//如果都相等
if (a[pa1] < b[pb2]) {//用最慢的马消耗齐王最快的马
qw++;
}
pb2--;
pa1++;
}
}
}
cout << tj - qw << endl;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~