题意：给出数量相等的大王的马的速度与田忌的马的速度，找一个最好的方案使田忌战绩最优，赢一局200元。
Analyse:
传闻这是个贪心算法的题。
为体现田忌的马的生存价值，总思想是能跑赢的就要跑赢能大王赢的最快的马，不能赢的（包括输的）必须要输给大王最快的马。
具体做法：
1.田忌最慢的马若能赢大王最慢的马就赢，一定输的就跟大王的最快的马比。
2.若田忌最慢的马跟大王最慢的马平局，则比较田忌最快的马与大王最快的马，能赢则赢；只要不能赢就让大王的快马对田忌的慢马。
不能赢的情况包括：
平：若能平局，则田忌最快的马比大王剩下的马都快。让大王最快的马赢田忌最慢的马，田忌的快马起码扳回一局，而且增加后面的马的胜率。
败：反正都输给大王的快马，给他一个肉盾（慢马），留下田忌的快马。
预备工作：排序
Recommend
JGShining
View Code
1 #include<stdio.h>
2 int main()
3 {
4 int n,i,j,temp,max,reward;
5 int Tian[1024],King[1024];
6 int SlowT,FastT,SlowK,FastK,counter;
7 while(scanf("%d",&n)&&n)
8 {
9 for(i=0;i<n;i++)
10 scanf("%d",&Tian[i]);
11 for(i=0;i<n;i++)
12 scanf("%d",&King[i]);
13 for(i=0;i<n-1;i++)
14 {
15 max=i;
16 for(j=i+1;j<n;j++)
17 {
18 if(Tian[max]<Tian[j])
19 max=j;
20 }
21 temp=Tian[max];
22 Tian[max]=Tian[i];
23 Tian[i]=temp;
24 }
25 for(i=0;i<n-1;i++)
26 {
27 max=i;
28 for(j=i+1;j<n;j++)
29 {
30 if(King[max]<King[j])
31 max=j;
32 }
33 temp=King[max];
34 King[max]=King[i];
35 King[i]=temp;
36 }
37 reward=0;
38 SlowT=SlowK=n-1;
39 FastK=FastT=0;
40 for(counter=0;counter<n;counter++)
41 {
42 if(Tian[SlowT]>King[SlowK])
43 {
44 SlowT--;
45 SlowK--;
46 reward++;
47 }
48 else if(Tian[SlowT]<King[SlowK])
49 {
50 reward--;
51 SlowT--;
52 FastK++;
53 }
54 else
55 {
56 if(Tian[FastT]>King[FastK])
57 {
58 reward++;
59 FastK++;
60 FastT++;
61 }
62 else
63 {
64 if(Tian[SlowT]<King[FastK])
65 reward--;
66 FastK++;
67 SlowT--;
68 }
69 }
70 }
71 reward*=200;
72 printf("%d\n",reward);
73 }
74 return 0;
75 }