思路:
先排序,然后比较,比较分以下情况。
田忌最快的马比王的快,可以直接赢下他,此时收益最大
田忌最快的马不如王的快,则此时是必输局面,用最慢的马输给他,为后续比较提供更大的胜算
田忌最快的马和王的一样快,比较最慢的马
分三种情况
田忌最慢的马比王的快,则用最慢的马赢王最慢的马,收益最大
田忌最慢的马比王的慢,又是一个必输局面,用最慢的马输王最快的马,为后续提供更多胜算
田忌最慢的马和王的一样慢,用最慢的马输与王比(可能输也可能平局),为后续比较提供更多胜算
然后模拟就好了
emm,答案可能是负数,我用了快速输入输出,在输出的时候没考虑到这一点,因此wa了好多发。
#include<cstdio>
//using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
int p(int a[], int l, int r){
int s = a[l];
int i, j;
i = l;
j = r;
while (i < j){
while (i < j && a[j] >= s)j--;
if (i < j)a[i++] = a[j];
while (i < j && a[i] < s)i++;
if (i < j)a[j--] = a[i];
}
a[i] = s;
return i;
}
void sort(int a[], int l, int r){
if (l < r){
int k = p(a, l, r);
sort(a, l, k - 1);
sort(a, k + 1, r);
}
}
template <class T>
bool read(T & a){
a = 0;
int flag = 0;
char ch;
if((ch = getchar()) == '-'){
flag = 1;
}
else if(ch >= '0' && ch <= '9'){
a = a * 10 + ch - '0';
}
while ((ch = getchar()) >= '0' && ch <= '9'){
a = a * 10 + ch - '0';
}
if(flag)a = -a;
return true;
}
template <class T, class ... R>
bool read(T & a, R & ... b){
if(!read(a))return 0;
read(b...);
}
template <class T>
bool out(T a){
if(a < 0)putchar('-');
if(a >= 10)out(a / 10);
putchar(a % 10 + '0');
return true;
}
template <class T, class ... R>
bool out(T a, R ... b){
if(!out(a))return 0;
out(b...);
}
int n;
int a[1100], b[1100];
void in(){
rep (i, 0, n - 1){
read(a[i]);
}
rep (i, 0, n - 1){
read(b[i]);
}
}
void solve(){
int ans = 0;
sort(a, 0, n - 1);
sort(b, 0, n - 1);
int la, lb, ra, rb;
la = lb = 0;
ra = rb = n - 1;
rep (i, 0, n - 1){
if (a[ra] > b[rb]){
ans += 200;
ra--;
rb--;
}
else if (a[ra] < b[rb]){
ans -= 200;
rb--;
la++;
}
else {
if (a[la] < b[lb]){
la++;
rb--;
ans -= 200;
}
else if (a[la] > b[lb]){
la++;
lb++;
ans += 200;
}
else {
if (a[la] < b[rb])ans -= 200;
la++;
rb--;
}
}
}
if (ans < 0){
putchar('-');
ans = -ans;
}
out(ans);puts("");
}
int main(){
while (read(n) && n){
in();
solve();
}
return 0;
}