小码哥和小码弟打开了pvp模式！但是因为不想伤着对方，他们决定用各自在不同星球上收服的宠物来进行多场战斗。
宠物伙伴的战力由多种因素决定，比如体型、性格和与主人的关系等等。借由阿特拉斯的算力，最终每只宠物的战力可以算成一个具体战力数值，战力数值更高的在一场战斗中必赢。
小码哥和小码弟各自有n只宠物，每只宠物都要和对方的一只宠物参加战斗且只参加一次战斗。双方各自有自己的宠物出战顺序，且双方不知道对方的顺序。每场战斗赢家会得两分，输家不得分，平局各得一分。现在需要你算出小码哥最多和最少能得多少分。
格式
输入格式：
第一行一个整数n，表示宠物数；
接下来n行，每行一个整数描述小码哥宠物的战力值；
再接着n行，描述小码弟宠物的战力值。
输出格式：
两个整数，用一个空格隔开，分别表示小码哥能得到的最多和最少分数。
样例 1
输入：
3
3
1
2
4
1
1
输出：
4 3
备注
其中：1≤n≤100000，0≤战力数值≤10000000
思路：分数总和一定，为2n，即若求甲最少得多少分，则求(2n-乙最多拿多少分)
注意：此题与田忌赛马不同，田忌赛马是每种马都不如对手的，而此题没有这个条件
贪心策略：
①如果甲最强>乙最强，则强打强
②如果甲最弱>乙最弱，则弱打弱
③如果甲最弱a<=乙最弱b，则让甲最弱a打乙最强c（牺牲a去打c，保证利益最大化）
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int n; int solve(int a[], int b[]) { // 求a打b，a的最大得分 int ans = 0, al = 1, ar = n, bl = 1, br = n; while (al <= ar) { if (a[ar] > b[br]) { // 最强打最强 ans += 2; ar--, br--; } else if (a[al] > b[bl]) { // 最弱打最弱 ans += 2; al++, bl++; } else if (a[al] <= b[bl]) { // 如果甲最弱a<=乙最弱b，所以牺牲a去打乙最强c if (a[al] == b[br]) { ans++; } al++, br--; } } return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> b[i]; } sort(a, a + n + 1); // 升序 sort(b, b + n + 1); cout << solve(a, b) << " " << n * 2 - solve(b, a); return 0; }
