当前位置：首页 > news >正文

算法打卡——田忌赛马问题

news 来源：原创 2024/9/20 5:57:49

问题简介：就是一个贪心的思想，下面上题目

要求示例输出输入

大体上先比较快马，田的快马与王的快马

其次比较田的慢马与王的慢马，

两处边界比较完全之后可以直接贪心了

几份示例的代码

代码一

#include <bits/stdc++.h>
using namespace std;
int main() {int n;int tian[2002], qi[2002];while(cin>>n,n!=0){for (int i = 1; i <= n; i++)cin >> tian[i];for (int i = 1; i <= n; i++)cin >> qi[i];sort(tian + 1, tian + 1 + n);sort(qi + 1, qi + 1 + n);int tm, qm, tk, qk;tm = 1, qm = 1;tk = n, qk = n;int money = 0;for (int i = 1; i <= n; i++) {if (tian[tk] > qi[qk]) { money += 200;tk--, qk--;} else if (tian[tk] < qi[qk]) { money -= 200;tm++, qk--;} else {if (tian[tm] > qi[qm]) { money += 200;tm++, qm++;} else {if (tian[tm] < qi[qk]) {money -= 200;tm++, qk--;}}}}cout << money<<endl;} return 0;
}

代码二，这个用stl写的，但是有个问题，就是如果用while输入，每调用一次函数，money变量会加倍，这个问题怀疑与vector的特性有关，以后再深究

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;int count1=0;//胜利场次 
int count2=0;//平局场次 
int cnt=0;//败北场次 int tianRac(vector<long long>Tian, vector<long long>King, int n)
{int money = 0; // 田忌赢的钱int tianh = 0, tiane = n-1, kingh = 0, kinge = n-1;// 分别标记田忌马队和齐王马队的最快和最慢的马// 共有 n 次比赛，每进行一次，就换下一匹马for (int i = 0; i < n; i++){// 田忌快马比齐王快马快时，那就和他一较高下if (Tian[tianh] > King[kingh]){count1++; tianh++;// 下一个kingh++;// 下一个}// 田忌快马不比齐王快马快时，比较慢马是否能赢 else {// 田忌的慢马比齐王的慢马快时if (Tian[tiane] > King[kinge]) {count1++; tiane--;kinge--;}// 田忌的慢马不比齐王的慢马快，就用慢马和他快马比else if (Tian[tiane] < King[kingh]) {cnt++;tiane--;kingh++;}}}count2=n-count1-cnt; money=count1*200-cnt*200;return money;	//返回田忌赢的钱
}
int main()
{int n;// 比赛双方马的数量cout << "公等马几何" << endl;cin >> n;vector <long long> tian;vector <long long> king;long long x;cout << "将军 马之疾" << endl;for (int i = 0; i < n; i++){cin >> x ;tian.push_back(x);}cout << "王 马之疾" << endl;for (int i = 0; i < n; i++){cin >> x ;king.push_back(x);}// 降序排xusort(tian.begin(),tian.end(),greater<long long>());sort(king.begin(),king.end(),greater<long long>());int result = tianRac(tian, king, n);cout<<result<<endl;return 0;
}