C語言貪心(2)___田忌賽馬(Hdu 1052)
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?"
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 hZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnNlIHJhY2luZyBwcm9ibGVtIGNhbiBiZSBzaW1wbHkgdmlld2VkIGFzIGZpbmRpbmcgdGhlIG1heGltdW0gbWF0Y2hpbmcgaW4gYSBiaXBhcnRpdGUgZ3JhcGguIERyYXcgVGlhbg=="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, which 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 the 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
20 19
22 18
0
Sample Output
200
0
0
題意：田忌賽馬。田忌和齊王各有n匹馬，輸入田忌的馬的速度和齊王的馬的速度。每一輪田忌贏了就得200兩銀子，平就得0兩，輸了就失去200兩銀子。問田忌最多能得到多少。
這道題可以使用 DP、給每匹馬連線賦權變為二分圖最佳匹配、貪心.
這裡講講貪心的方法：
1.當田忌最慢的馬比齊王最慢的馬快，贏一場先
2.當田忌最慢的馬比齊王最慢的馬慢，和齊王最快的馬比，輸一場
3.當田忌最快的馬比齊王最快的馬快時，贏一場先。
4.當田忌最快的馬比齊王最快的馬慢時，拿最慢的馬和齊王最快的馬比，輸一場。
5.當田忌最快的馬和齊王最快的馬相等時，拿最慢的馬來和齊王最快的馬比.
田忌賽馬貪心的正確性證明。
先說簡單狀況下的證明：
1.當田忌最慢的馬比齊王最慢的馬快，贏一場先。因為始終要贏齊王最慢的馬，不如用最沒用的馬來贏它。
2.當田忌最慢的馬比齊王最慢的馬慢，和齊王最快的馬比，輸一場。因為田忌最慢的馬始終要輸的，不如用它來消耗齊王最有用的馬。
3.當田忌最慢的和齊王最慢的馬慢相等時，分4和5討論。
4.當田忌最快的馬比齊王最快的馬快時，贏一場先。因為最快的馬的用途就是來贏別人快的馬，別人慢的馬什麼馬都能贏。
5.當田忌最快的馬比齊王最快的馬慢時，拿最慢的馬和齊王最快的馬比，輸一場，因為反正要輸一場，不如拿最沒用的馬輸。
6.當田忌最快的馬和齊王最快的馬相等時，這就要展開討論了,貪心方法是，拿最慢的馬來和齊王最快的馬比.
前面的證明像公理樣的，大家一看都能認同的，沒有異議的，就不細說了。
證明：田忌最快的馬和齊王最快的馬相等時拿最慢的馬來和齊王最快的馬比有最優解。
1）假設他們有n匹馬，看n=2的時候.
a1 a2
b1 b2
因為 田忌最快的馬和齊王最快的馬相等 所以a1=b1,a2=b2 所以這種情況有2種比賽方式，易得這兩種方式得分相等。
2）當數列a和數列b全部相等等時(a1=b1,a2=b2...an=bn)，顯然最慢的馬來和齊王最快的馬比有最優解,可以贏n-1長，輸1場，找不到更好的方
法了。
3）當數列a和數列b元素全部相等時(a1=b1=a2=b2...=an=bn)，無法贏也不輸。
現在假設n匹馬時拿最慢的馬來和齊王最快的馬比有最優解，證明有n+1匹馬時拿最慢的馬來和齊王最快的馬比也有最優解。
數列
a1 a2 a3 a4...an an+1
b1 b2 b3 b4...bn bn+1
其中ai>=ai-1,bi>=bi-1
數列a和數列b不全部相等時，拿最慢的馬來和齊王最快的馬比數列得到數列
(a1) a2 a3 a4...an an+1
b1 b2 b3 b4...bn (bn+1)
分4種情況討論
1.b1=b2,an=an+1
則有
a2 a3 a4...an
b2 b3 b4...bn
其中a2>=a1,a1=b1,b1=b2,得a2>=b2(此後這種大小關系不再論述）,an>=bn.
此時若a2=b1,根據歸納假設，有最優解，否則a2>根據前面“公理”論證有最優解。
當且僅當a數列,b數列元素全部相等時有an+1=b1,已證得，所以an+1>b1，贏回最慢的馬來和齊王最快的馬比輸的那一場。
2.b1<=b2,an=an+1
交換 b1,b2的位置，
數列
(a1) a2 a3 a4...an an+1
b2 b1 b3 b4...bn (bn+1)
此時 a2>=a1,an>=bn,
對於子表
a2 a3 a4...an
b1 b3 b4...bn
根據前面“公理”或歸納假設，有最優解。
an+1>=b2, 當且僅當b2=b3=b4=..=bn+1時有an+1=b2，這種情況，a中其它元素<=b1,b2,b3,b4..bn,對於這部分來說，能贏 x盤(x<=n)，假如不拿最慢的馬來和齊王最快的馬比則拿最快的馬來和齊王最快的馬比，此時平一盤，能贏x-1盤，而拿最慢的馬來和齊王最快的馬 比，輸一盤能贏x盤，總的來說，還是X這個數，沒有虧。
3.b1=b2,an<=an+1
4.b1<=b2,an<=an+1證明方法類似，不再重復。
以證得當有n+1匹馬的時候，田忌和齊王最快最慢的馬速度相等時，拿最慢的馬來和齊王最快的馬比有最優解，已知當n=2時成立，所以對於n>2且為整數（廢話，馬的只數當然是整數）時也成立。當n=1時....這個似乎不用討論.
樣例：
#include
#include
#include
#include
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n,money;
int a[1000],b[1000];
while(cin>>n)
{
if(!n)
break;
for(int i=0;i>a[i];
for(int i=0;i>b[i];
sort(a,a+n,cmp);
sort(b,b+n,cmp);
money=0;
for(int i=n-1;i>=0;i--)
{
if(a[i]>b[i])
{
money++;
}
else if(a[i]b[0])
{
money++;
for(int j=0;jb[0])
{
money++;
for(int j=0;j
