简版田忌赛马
作者 usx程序设计类课程组
单位 绍兴文理学院
这是一个简版田忌赛马问题,具体如下:
田忌与齐王赛马,双方各有n匹马参赛,每场比赛赌注为200两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,请写一个程序帮助田忌计算他最多赢多少两黄金(若输,则用负数表示)。
简单起见,保证2n匹马的速度均不相同。
输入格式:
首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。
每组测试数据输入3行,第一行是n(1≤n≤100) ,表示双方参赛马的数量,第2行n个正整数,表示田忌的马的速度,第3行n个正整数,表示齐王的马的速度。
输出格式:
对于每组测试数据,输出一行,包含一个整数,表示田忌最多赢多少两黄金。
输入样例:
4
3
92 83 71
95 87 74
2
20 25
21 12
10
1 2 3 24 5 6 7 8 9 12
11 13 15 19 22 34 14 21 44 99
4
10 15 16 37
14 20 30 40
输出样例:
200
400
-1200
0
答案显示错误
#include
using namespace std;
int main(){
int a,c,d,e,g;
cin>>e;
int s[100];
int f[100];
g=0;
while(cin>>a){
g=g+1;
for(int i=0;i<100;i++){
s[i]=0;
f[i]=0;
}
for(int i=0;i>s[i];
}
for(int i=0;i>f[i];
}
for (int i=0;ifor(int j=a-1;j>i;j--){
if(s[j]c=s[j];
s[j]=s[j-1];
s[j-1]=c;
}
}
}
for (int i=0;ifor(int j=a-1;j>i;j--){
if(f[j]>f[j-1]){
c=f[j];
f[j]=f[j-1];
f[j-1]=c;
}
}
}
d=0;
int flag=0;
for (int i=0;id=d-200;
flag=0;
for (int j=0;jif(s[j]>f[i]){
d=d+400;
s[j]=0;
j=a;
flag=1;
}
if(s[j]==f[i]){
d=d+200;
s[j]=0;
j=a;
flag=1;
}
}
if(flag==0){
for (int j=0;jif (s[j]!=0) {
s[j]=0;
j=a;
}
}
}
}
cout<
运行结果及详细报错内容
显示答案错误
我的解答思路和尝试过的方法,不写自己思路的,回答率下降 60%
先冒泡排序,然后先拿齐王最快的马,去匹配田的马
我想要达到的结果,如果你需要快速回答,请尝试 “付费悬赏”
望采纳
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 计算田忌最多赢多少两黄金
int calculate(const vector<int>& tian, const vector<int>& qi)
{
int result = 0;
for (int i = 0, j = 0; i < tian.size() && j < qi.size(); )
{
if (tian[i] < qi[j])
{
result -= 200;
i++;
j++;
}
else
{
// 如果田忌的马速度比齐王的马速度快,
// 则田忌可以选择与齐王最慢的马进行比赛
if (tian[i] > qi[qi.size() - 1])
{
result += 200;
i++;
qi.pop_back();
}
// 如果田忌的马速度比齐王的马速度慢,
// 则田忌可以选择与齐王最快的马进行比赛
else
{
result -= 200;
j++;
tian.erase(tian.begin() + i);
}
}
}
return result;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
vector<int> tian(n), qi(n);
for (int i = 0; i < n; i++)
cin >> tian[i];
for (int i = 0; i < n; i++)
cin >> qi[i];
sort(tian.begin(), tian.end());
sort(qi.begin(), qi.end());
cout << calculate(tian, qi) << endl;
}
return 0;
}