贪婪算法之田忌赛马
贪婪算法之田忌赛马
【问题描述】
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
输入
第一行为一个正整数n (n <= 2000) ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
输出
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
输入示例
3
92 83 71
95 87 74
输出示例
200
C语言的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<stdio.h>
#define MAX 1000
int t[MAX],w[MAX];
void sort(int n,int t[])
{
int i,j,temp;
for(i=1;i<=n;i++)
for(j=1;j<=n-i;j++)
{
if(t[j]>t[j+1])
{
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
}
}
}
int main()
{
int n;
printf("请输入双方赛马数量n:");
scanf("%d",&n);
printf("请录入田忌赛马速度:");
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
}
printf("请录入齐王赛马速度:");
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
sort(n,t);
sort(n,w);
int tj_min=1,tj_max=n,qw_min=1,qw_max=n,count=0,sum;
while(n--)
{
if(t[tj_max]>w[qw_max])
{
count++;
tj_max--;
qw_max--;
}
else if(t[tj_max]<w[qw_max])
{
count--;
tj_min++;
qw_max--;
}
else
{
if(t[tj_min]>w[qw_min])
{
count++;
tj_min++;
qw_min++;
}
else
{
if(t[tj_min]<w[qw_max])
count--;
tj_min++;
qw_max--;
}
}
}
sum=count*200;
printf("最终田忌最多可以拿到%d的奖金\n",sum);
return 0;
}
|
运行截图
