hdoj 1052 Tian Ji -- The Horse Racing【田忌赛马，贪心】

灰太狼 2022-08-04 11:44 181阅读 0赞

# Tian Ji -- The Horse Racing【田忌赛马】 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 22498    Accepted Submission(s): 6574**

![1052-1.gif][]

（田忌赛马的故事应该都知道吧，故事内容就不介绍了）  
题目大意 ：给你一个整数n（n为零结束），表示田忌和齐王各有n匹马，接下来的两行各有n个数，n个数对应n匹马的速度，第一行是田忌的马，第二行市齐王的马，两匹马比赛，快的那只获胜，获胜的一方可以从失败的一方那里拿200钱，若平局，就各不相欠，求，田忌用孙膑的策略，最多能赢多少钱？

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

思路：先对马进行排序；升序或者降序都行（笔者用的是sort()  默认排序，即升序），

接着就可以比较了，情况如下：

①若田忌最快的马比齐王那个最快的马还快，直接赢，原本次快的，现在变成最快的；

②若田忌最快的马与期望最快的马一样快，则比较田忌与齐王最慢的马，此处情况如下：\{

Ⅰ.田忌最慢的马比齐王最慢的马快，直接赢，原本次慢的，现在变成最慢的；

Ⅱ.两最慢的马一样快\{

㈠  if  田忌最慢的马和齐王最快的马一样快，平局；

㈡ else  田忌用最慢的马和齐王最快的马比，输掉比赛，田忌次慢的马成为最慢的马，齐王次快的恶骂变成最快的马；

Ⅲ.若田忌最慢的马比齐王那个最慢的马慢， 田忌用最慢的马和齐王最快的马比，输掉比赛，田忌次慢的马成为最慢的马，齐王次快的恶骂变成最快的马；

③若田忌最快的马比齐王那个最快的马慢， 田忌用最慢的马和齐王最快的马比，输掉比赛，田忌次慢的马成为最慢的马，齐王次快的恶骂变成最快的马；

这里提供一组数据，据说这组数据能过，题中给的例子也能过，咱代码就能过；

8          【答案：800】

11 9 8 8 8 4 3 2  
11 9 8 8 8 4 3 2

Accept代码（用c++格式提交）

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[1001],b[1001],s[1001],v[1001];
    int main(){
    	int n,i,j;
    	while(scanf("%d",&n),n){
    		memset(v,0,sizeof(v));
    		memset(s,0,sizeof(s));
    		for(i=0;i<n;i++)
    			scanf("%d",&a[i]);
    		for(i=0;i<n;i++)
    			scanf("%d",&b[i]);
    		sort(a,a+n);
    		sort(b,b+n);
    		int q=0,k=0,t=n-1,f=n-1;
    		int total=0;
    		while(t>=q){
    			if(a[t]>b[f]){					//①
    				t--;
    				f--;
    				total+=200;
    			}
    			else if(a[t]==b[f]){			//②
    				if(a[q]>b[k]){						//Ⅰ
    					q++;
    					k++;
    					total+=200;
    				}
    				else if(a[q]==b[k]){				//Ⅱ
    					if(a[q]<b[f]){							//㈠
    						f--;
    						q++;
    						total-=200;
    					}
    					else{									//㈡
    						f--;
    						q++;
    					}
    				}
    				else{								//Ⅲ	
    					f--;
    					q++;
    					total-=200;
    				}
    			}
    			else{							//③
    				f--;
    				q++;
    				total-=200;
    			}
    		}
    		printf("%d\n",total);
    	}
    	return 0;
    }

[1052-1.gif]: /images/20220731/1d1236393fd84a90a5421fa112a1d8f0.png