Tian Ji -- The Horse Racing
田忌赛马,还是English,要不是看题目,我都被原题整懵了,直接上Chinese吧
Descriptions:
田忌和齐王赛马,他们各有n匹马,依次派出一匹马比赛,赢了加200,输了减200,平局不加钱,问如何安排马的出场顺序,使得田忌赢的钱最多
Input
输入最多包含 50 组测试数据。对于每组测试数据,第一行包括一个正整数 n (n ≤ 1000),表示每一方的马的数目。第二行中的 n 个整数,表示田忌的马的速度。第三行中的 n 个整数,表示齐王的马的速度。在最后一组测试数据之后,是只包含单个 0 的一行。
Output
对于每组测试数据,输出包含单个数的一行,表示田忌将从齐王那里赢得银两的最大值。
Sample Input
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
Sample Output
200 0 0
题目链接:
https://vjudge.net/problem/OpenJ_Bailian-2287
题解都在代码上
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define ME0(x) memset(x,0,sizeof(x)) using namespace std; int n; int a[1005]; int b[1005]; int main() { while(cin>>n,n) { ME0(a); ME0(b); int sum=0; for(int i=0; i<n; i++) cin>>a[i];//田忌的马 for(int i=0; i<n; i++) cin>> b[i];//齐王的马 sort(a,a+n);//排序 sort(b,b+n); int l1=0; int l2=0; int r1=n-1; int r2=n-1; while(l1<=r1) { //田忌最快的马比齐王最快的马快,则两者比 if(a[r1]>b[r2]) { sum+=200; --r1; --r2; } //田忌最快的马比齐王最快的马慢,则用田忌最慢的马和齐王最快的马比 if(a[r1]<b[r2]) { sum-=200; ++l1; --r2; } //速度相等 if(a[r1]==b[r2]) { //田忌最慢的马比齐王最慢的马快,则这两匹马比 if(a[l1]>b[l2]) { sum+=200; ++l1; ++l2; }//否则,用田忌最慢的马和齐王最快的马比 else { if(a[l1]<b[r2])//田忌最慢的马比齐王最快的马快 sum-=200;//加200 ++l1;//否则平局 --r2; } } } cout<<sum<<endl; } }