POJ 2287 Tian Ji -- The Horse Racing (贪心)

题目链接：POJ 2287

Description

Input

Output

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

Source

Shanghai 2004

Solution

题意

田忌赛马，田忌和齐王都有 \(n\) 匹马，赢一局得 \(200\)，输一局失 \(200\)，平局财产不动。求田忌最多能赢多少钱。

思路

贪心

首先拿田忌最快的马与齐王最快的马比。

如果田忌的马快就赢一场，否则用最慢的马去比，输一场。

如果田忌最快的马与齐王最快的马一样快，则拿田忌最慢的马与齐王最慢的马比。

Code

#include <iostream>
#include <algorithm>
using namespace std;
int a[1010], b[1010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n) {
        if(n == 0) break;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for(int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        sort(a, a + n);
        sort(b, b + n);
        int min1 = 0, min2 = 0;
        int max1 = n - 1, max2 = n - 1;
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            if(a[max1] > b[max2]) {  // 田忌最快的马比齐王最快的马快
                ++ans;
                max1--;
                max2--;
            } else if(a[max1] < b[max2]) {  // 田忌最快的马比齐王最快的马慢
                --ans;
                min1++;
                max2--;
            } else {  // 田忌最快的马与齐王最快的马一样快
                if(a[min1] > b[min2]) {  // 田忌最慢的马比齐王最慢的马快
                    ++ans;
                    min1++;
                    min2++;
                } else {
                    if(a[min1] < b[max2]) {  // 田忌最慢的马比齐王最慢的马慢
                        --ans;
                    }
                    min1++;
                    max2--;
                }
            }
        }
        cout << ans * 200 << endl;
    }
    return 0;
}