田忌和国王各有n匹马,
田忌n匹马的速度为a_1, a_2, a_3, ..., a_na1,a2,a3,...,an。
国王n匹马的速度为b_1, b_2, b_3, ..., b_nb1,b2,b3,...,bn。
现在要进行n轮比赛,每轮双方各安排一匹马(比过的不能再上场)进行比赛,速度快的赢200两银子,速度慢的输200两银子,速度一样则不赢也不输。
现在由我们来任意安排马的出场次序,问田忌最多可以赢多少两银子。
输入
第一行输入一个整数n (1 le n le 1000)n(1≤n≤1000)。
第二行输入n个整数a_1, a_2, a_3, ..., a_n (1 le a_i le 2000)a1,a2,a3,...,an(1≤ai≤2000),表示田忌马的速度。
第三行输入n个整数b_1, b_2, b_3, ..., b_n (1 le b_i le 2000)b1,b2,b3,...,bn(1≤bi≤2000),表示国王马的速度。
输出
田忌最多可以赢多少两银子。
样例
输入
复制
3 92 83 71 95 87 74
输出
复制
200
提示
子任务1,20分,1 le n le 91≤n≤9。
子任务2,80分,1 le n le 10001≤n≤1000。
#pragma warning(disable:4996) #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> #include <set> #define MAX 2001 using namespace std; int main() { int n; int ans = 0; scanf("%d", &n); std::vector<int> t(n), g(n); for (int i = 0; i < n; i++) { scanf("%d", &t[i]); } for (int i = 0; i < n; i++) { scanf("%d", &g[i]); } sort(t.begin(), t.end()); sort(g.begin(), g.end()); int l = 0, r = n - 1; int j = 0; for (int i = n - 1; i >= j; i--) { if (g[i] > t[r])//国王最快的比田最快的快,拿最慢的和国王最快的比,横竖要输就拿最菜的去输 { ans -= 200; l++; } else if(g[i] < t[r])//国外最快的没有田最快的快,直接比,不要拿田其他的和国王最快的比了,可能会输结果更差,最快的马当然要用来压制最快的 { ans += 200; r--; } else if(g[j] >= t[l])//最快的速度都一样,平局不赚钱,看最慢的,国王的比较快,那么田最慢的总要输或平一局倒不如用来消耗国王最快的 { ans -= (g[i] > t[l]) * 200; l++; } else//田的快一些就直接最慢的比 { ans += 200; l++; j++; i++; } } printf("%d", ans); return 0; }