杭电 Tian Ji -- The Horse Racing

杭电赛马题题解

杭电 Tian Ji -- The Horse Racing

Tian Ji -- The Horse Racing
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Here is a famous story in Chinese history.

"That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others."

"Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser."

"Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian."

"Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match."

"It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?"

hdu <wbr>1052 <wbr>Tian <wbr>Ji <wbr>-- <wbr>The <wbr>Horse <wbr>Racing

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching...

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses --- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

In this problem, you are asked to write a program to solve this special case of matching problem.
Input
The input consists of up to 50 test cases. Each case starts with a positive integer n (n <= 1000) on the first line, wh
ich is the number of horses on each side. The next n integers on the second line are the speeds of Tian’s horses. Then the next n integers on th

杭电赛马题题解

e third line are the speeds of the king’s horses. The input ends with a line that has a single 0 after the last test case.
Output
For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.
Sample Input
3
92 83 71
95 87 74
2 20 20
20 20
2 2
0 19
22 18
0
Sample Output
200
0
0

终于遇到一道值得题解报告的题了，这是道贪心的题，在杭电提交了13次10次是WA, 仔细想想，觉得还是思考的方向不对后来百度了下终于大彻大悟，百度上的基本是用C++实现，自己用C语言写了个，先来算法吧：
题目大意：田忌和国王赛马，给出马的数量n，然后是田忌的n匹马，国王的n匹马。问田忌最多可以赢得多少比赛（一场200块）。

因为比赛的时候，是国王先出马，然后田忌再出，田忌有主动权上的优势。
先对田忌和国王的马进行排序。
贪心的策略：
一、当田忌最快的马比国王最快的马快时，用田忌最快的马赢国王最快的马。
二、当田忌最快的马比国王最快的马慢时，用田忌最慢的马输给国王最快的马。
三、当田忌最快的马跟国王最快的马一样快时，分情况：
1、当田忌最慢的马比国王最慢的马快，那么用田忌最慢的马赢国王最慢的马
2、当田忌最慢的马比国王最慢的马慢，那么用田忌最慢的马输给国王最快的马
3、当田忌最慢的马跟国王最慢的马相等的时候，用田忌最慢的马跟国王最快的马比
下面是网上的证明：
证明一、：假设现在国王最快的马是K，田忌最快的马是T，如果存在一种更优的比赛策略，让T的对手不是K，而使得田忌赢更多的钱的话，那么设此时K的对手是t，T的对手是k：( T>K &&T>t && K>k)
1、 若t>K，则有T>k，t>K。这个结果和T>K，t>k是相同的。
2、 若k<t≤K，则有T>k，t≤K。这个结果不如T>K，t>k来得优秀。
3、 若t≤k≤K，则有T>k，t≤K。这个结果和T>K，t≤k是相同的。
由此可知，交换各自对手后，一定不会使得结果变劣，那么假设是不成立的。

证明二、：因为田忌最快的马比国王最快的马慢，所以田忌所有的马都比国王最快的马慢，也就是说此时田忌的所有马都赢不了国王的马，而出于贪心的思想，应该保留相比之下更快的马，因此用最慢的马去输一定不会比用别的马去输来得劣。
其实上面这两个很容易就想得到，最难的是相等的时候。因为不可以直接让田忌最快的马跟国王最快的马打平，或者直接用最慢的马去输给国王最快的马。（存在反例）

下面是我的代码：

#include&l
t;stdio.h>
void swap(int *a,int *b)
{
int temp= *a;
(*a) = (*b);
(*b) = temp;
}
int main()
{
int n,i,k,mina,maxa,sum,maxb,minb;

杭电赛马题题解

int a[1010],b[1010];

while(scanf("%d",&n)!=EOF&&n)
{
for(i = 0;i < n; i++)
scanf("%d",&a[i]);
for(i = 0;i < n; i++)
scanf("%d",&b[i]);

for(i = n-1 ;i >= 0; --i)
{
for(k = 0;k < i; k++)
{
if(a[i] < a[k])
swap(&a[i],&a[k]);
if(b[i] < b[k] )
swap(&b[i],&b[k]);
}
}
k=0;
mina=0;
minb=0;
maxa=n-1;
maxb=n-1;
for(i = 0; i < n; i ++)
{
if(a[maxa] > b[maxb])
{
maxa--;
maxb--;
k++;
}
else if(a[maxa] < b[maxb])
{
mina++;
maxb--;
k--;
}
else
{
if(a[mina] < b[minb])
{
maxb--;
mina++;
k--;
}
else if(a[mina] > b[minb])
{
mina++;
minb++;
k++;

}
else
{
if(a[mina] < b[maxb])
{
maxb--;
mina++;
k--;
}
}
}
}
sum = 200 * k;
printf("%d\n",sum);
}
return 0;
}

本文来源：https://www.bwwdw.com/article/94s4.html