hdu_1052-Tian Ji -- The Horse Racing
/* 题目大意：田忌赛马 * 解题思路：这个题主要是想清楚怎样的比较方式能够将优势最大化 */#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MAX 1001int a[MAX], b[MAX];bool cmp(int a, int b){ return a > b;}int main(int argc, char const *argv[]){#ifndef ONLINE_JUDGE freopen("test.in", "r", stdin);#endif int cnt, ans, num1, num2; while( scanf("%d", &cnt), cnt ) { num1 = 0; num2 = 0; for(int i = 0; i < cnt; i ++) { scanf("%d", &a[i]); } for(int i = 0; i < cnt; i ++) { scanf("%d", &b[i]); } sort(a, a + cnt, cmp); //按递减顺序排序 sort(b, b + cnt, cmp); int i = 0, j = 0, k = cnt - 1, l = cnt - 1; //分别为田上、王上、田下、王下的当前位置 for(int t = 0; t < cnt; t ++) { if( a[i] < b[j] ) { //田上 < 王上 拿田下 和 王上比 j ++; k --; num2 ++; } else if( a[i] > b[j] ) { //田上 > 王上 直接比 i ++; j ++; num1 ++; } else { //田上 = 王上 if( a[k] > b[l] ) { //田下 > 王下 拿田下 和 王下比 num1 ++; k --; l --; } else if( a[k] < b[l] ) { //田下 < 王下 拿田下 和 王上比 num2 ++; j ++; k --; } else if( a[k] < b[j] ) { //田下 = 王下 && 田下 < 王上 拿田下 和 王上比 num2 ++; k --; j ++; } } } ans = (num1 - num2) * 200; printf("%d\n", ans); } return 0;}