ACM | Tian Ji -- The Horse Racing

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 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.

这里有一个中国历史上著名的故事。

“那是大约2300年前的事了，田忌将军是齐国的一位大官，他喜欢和国王等人赛马。”

“田和王各有三匹不同级别的马，分别是普通级、高级级、超级级。规则是一场比赛进行三轮，每匹马必须用完一轮。单场获胜者 败者得两百银元。”

“国王是全国最有权势的人，他的马非常好，每一级他的马都比田的好。因此，国王每次从田那里拿走六百银子。”

“田忌对此并不高兴，直到他遇到了中国历史上最著名的将军之一孙膑。田忌利用了孙膑的一个小伎俩，在接下来的比赛中带回了两百银元，并获得了如此大的恩惠。 ”

“这是一个相当简单的技巧，用他的普通级赛马与国王的超级赛马，他们肯定会输掉这一轮。但随后他的+击败了国王的普通级，他的超级击败了国王的+。多么简单的技巧 ……那么，您对田忌这个中国的高官有什么看法呢？

如果田忌生活在现在，他一定会嘲笑自己。 更重要的是，如果他现在参加ACM比赛，他可能会发现赛马问题可以简单地看作是在二部图中寻找最大匹配。 一侧画田的马，另一侧画国王的马。 每当田的一匹马能够击败国王的一匹马时，我们就在它们之间划一条边，这意味着我们希望建立这一对。 那么，赢得尽可能多的回合的问题就是找到这个图中的最大匹配。 如果存在平局，问题就变得更加复杂，他需要给所有可能的边分配权重0、1或-1，并找到一个最大加权完美匹配……

然而，赛马问题是二分匹配的一个非常特殊的例子。 该图由马的速度决定——速度较高的顶点总是击败速度较低的顶点。 在这种情况下，加权二分匹配算法对于处理该问题来说是一个过于先进的工具。

在此问题中，要求您编写一个程序来解决匹配问题的这种特殊情况。

输入格式:

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. 输入最多包含 50 个测试用例。 每个案例的第一行都以正整数 n (n <= 1000) 开头，它是每边的马匹数量。 第二行接下来的 n 个整数是田的马的速度。 那么第三行接下来的n个整数就是国王马匹的速度。 输入以最后一个测试用例后面有一个 0 的行结束。

输出格式:

For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars. 对于每个输入情况，输出一行包含一个数字，这是田忌将获得的最大银元金额。

输入样例:

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

输出样例:

200
0
0

示例代码：

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    while(n!=0){
        int a[1000];  //田忌
        int b[1000];  //国王
        for(int i=0;i<n;i++){
            scanf("%d",a+i);
        }
        for(int i=0;i<n;i++){
            scanf("%d",b+i);
        }
        int temp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(a[j]<a[j+1]){
                    temp = a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(b[j]<b[j+1]){
                    temp=b[j];
                    b[j]=b[j+1];
                    b[j+1]=temp;
                }
            }
        }
        int win_times=0;
        int cur_a=0;
        int cur_b=0;
        int tail_a=n-1;
        int tail_b=n-1;
        for(int i=0;i<n;i++){
            if(a[cur_a]>b[cur_b]){
                cur_a++;
                cur_b++;
                win_times++;
            }
            else if(a[tail_a]>b[tail_b]){
                tail_a--;
                tail_b--;
                win_times++;
            }else if(a[tail_a]<b[cur_b]){
                tail_a--;
                cur_b++;
                win_times--;
            }
        }
        printf("%d\n",win_times*200);
        scanf("%d",&n);
    }
    return 0;
}