Link

点击打开题目链接

Problem

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.

Mean

田忌(A)与齐王(B)赛马,两人个出N匹马,赢得一场比赛获得200两银子,输了赔200,平局不赔不赚。已知两人每匹马的速度,问A最多能获得多少两银子。

Analysis

首先把两个人各自的马按照速度排序,然后我们来分类讨论。

  1. A最快的马如果比B最快的马快,直接比下去,否则保留。
  2. A最慢的马比B最慢的马快,直接比下去,因为只用了A最慢的马就获得200两银子,值了。如果A最慢的马比B最慢的马慢,为了发挥A最慢马的价值,让他跟B最快的马比,败也值了。如果A最慢马和B最慢马同速,仍然用A最慢马和B最快马比较,此时,B最慢马可获得与A非最快马比较机会,也值了。

总的来说,就是发挥A中马的最大价值,贪心即可。

程序为了提高可读性,用两个list表示马,front()、back()分别表示最慢马和最快马。

Code

#include <bits/stdc++.h>
using namespace std;

int n, x;
list<int> A, B;

int main() {
    while(scanf("%d", &n), n) {
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            A.push_back(x);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            B.push_back(x);
        }
        A.sort(), B.sort();
        int win = 0;
        while(!A.empty()) {
            if(A.back() > B.back()) {
                ++win;
                A.pop_back(), B.pop_back();
            } else {
                if(A.front() > B.front()) {
                    ++win;
                    A.pop_front(), B.pop_front();
                } else {
                    if(A.front() < B.back()) --win;
                    A.pop_front(), B.pop_back();
                }
            }
        }
        printf("%d\n", win * 200);
    }
    return 0;
}

欢迎留言