题目地址：洛谷：【P2587】[ZJOI2008]泡泡堂 – 洛谷、BZOJ：Problem 1034. — [ZJOI2008]泡泡堂BNB

题目描述

第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。

题意简述

你和对手都有一队人，每边$n$个人。现在要求让你和对手的队伍两两对决，能力值高的一方获胜，得2分，若能力值相等平局，得1分，否则不得分。求出所有对决的设计中，你的最高可能得分与最低可能得分是多少。

输入输出格式

输入格式：
输入文件的第一行为一个整数n，表示每支代表队的人数。
接下来n行，每行一个整数，描述了n位浙江队的选手的实力值。
接下来n行，每行一个整数，描述了你的对手的n位选手的实力值。

输出格式：
输入文件中包括两个用空格隔开的整数，分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

输入输出样例

输入样例#1：

2
1
3
2
4

输出样例#1：

2 0

输入样例#2：

6
10000000
10000000
10000000
10000000
10000000
10000000
0
0
0
0
0
0

输出样例#2：

12 12

说明

样例说明
1： 我们分别称4位选手为A,B,C,D。则可能出现以下4种对战方式，最好情况下可得2分，最坏情况下得0分。
一 二 三 四
浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果
一号选手 A C 负 A D 负 B C 胜 B D 负
二号选手 B D 负 B C 胜 A D 负 A C 负
总得分 0 2 2 0
2： 对手都是认真学习的好孩子，不会打游戏。无论如何排列出场顺序都无法改变被蹂躏的结果。浙江队总能取得全胜的结果。

20％的数据中，1<=n<=10；
40％的数据中，1<=n<=100；
60％的数据中，1<=n<=1000；
100％的数据中，1<=n<=100000，且所有选手的实力值在0到10000000之间。

题解

贪心，我们想到了田忌赛马的模型，即用自己强的打对手强的，如果打不过就用一个最弱的送死。但是这种策略是有漏洞的，有可能拿去送死的最弱的可以将对手的最弱的打败，从而多获得2分，因此我们把这种情况也加入判断。
修改后的策略是，如果我方最强能赢对方最强，则进行这种对决；否则我方最弱如果能赢对方最弱，则以弱对弱；前两种情况都处理完了，再把一个最弱的拿去送死。
最低分数可以直接让对方跑一遍这个策略，然后用总得分减掉对方的最优得分即可。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int n, slf[MAXN], opp[MAXN], ls, rs, lo, ro;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        slf[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        opp[i] = readint();
    }
    std::sort(slf + 1, slf + n + 1);
    std::sort(opp + 1, opp + n + 1);
    int ans1 = 0, ans2 = 0;
    ls = lo = 1; rs = ro = n;
    while(ls <= rs) { 
        if(slf[rs] > opp[ro]) {
            ans1 += 2; rs--; ro--;
        } else if(slf[ls] > opp[lo]) {
            ans1 += 2; ls++; lo++;
        } else {
            ans1 += (slf[ls] == opp[ro]);
            ls++; ro--;
        }
    }
    ls = lo = 1; rs = ro = n;
    while(ls <= rs) {
        if(opp[ro] > slf[rs]) {
            ans2 += 2; rs--; ro--;
        } else if(opp[lo] > slf[ls]) {
            ans2 += 2; ls++; lo++;
        } else {
            ans2 += (opp[lo] == slf[rs]);
            lo++; rs--;
        }
    }
    printf("%d %d", ans1, 2 * n - ans2);
    return 0;
}