题目链接: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
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;
}