「BZOJ1034」[ZJOI2008]泡泡堂BNB

Description

第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由nn名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手,二号选手……,nn号选手捉对厮杀,共进行nn场比赛。每胜一场比赛得22分,平一场得11分,输一场不得分。最终将双方的单场得分相加得出总分,总分高的队伍晋级(总分相同抽签决定)。

作为浙江队的领队,你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。

当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,浙江队最终分别能得到多少分。

Input

输入文件的第一行为一个整数nn,表示每支代表队的人数。

接下来nn行,每行一个整数,描述了nn位浙江队的选手的实力值。

接下来nn行,每行一个整数,描述了你的对手的nn位选手的实力值。

Output

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

Sample Input

1
2
3
4
5
2
1
3
2
4

Sample Output

1
2 0

HINT

20%20\%的数据中,1n101\leq n\leq 10

40%40\%的数据中,1n1001\leq n\leq 100

60%60\%的数据中,1n10001\leq n\leq 1000

100%100\%的数据中,1n1000001\leq n\leq 100000,且所有选手的实力值在001000000010000000之间。

Solution

很显然aia_ibib_i先排好序。
如果aa最弱的比bb最弱的强,肯定要怼
否则 如果aa最强的比bb最强的强,肯定要怼
否则 用aa最弱的怼bb最强的。

第三个为什么是正确的?
考虑最弱的a1a_1和最强的ana_n,已经最弱的b1b_1和最强的bnb_n
a1a_1去怼bnb_n有两种情况
a1=bna_1=b_n,显然a1=a2==an=b1=b2==bna_1=a_2=\cdots =a_n =b_1=b_2=\cdots =b_n等价于aia_ibib_i怼。
否则肯定就是a1<bna_1<b_n了,此时收益是00,但是一定存在an>b1a_n>b_1,因为an=bn>b1a_n=b_n>b_1,最差就是用ana_n去怼b1b_1,否则肯定至少不差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210000;
int a[N], b[N], n;

int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
sort(a + 1, a + 1 + n);
sort(b + 1, b +1 + n);
int l1 = 1, r1 = n, l2 = 1, r2 = n;
int ans1 = 0, ans2 = 0;
for(int i = 1; i <= n; ++i) {
if(a[l1] > b[l2]) ++l1,++l2,ans1+=2;
else if(a[r1] > b[r2]) --r1,--r2,ans1+=2;
else {
ans1 += (a[l1] == b[r2]);
++l1,--r2;
}
}
l1 = 1, r1 = n, l2 = 1, r2 =n;
for(int i = 1; i <= n; ++i) swap(a[i], b[i]);
for(int i = 1; i <= n; ++i) {
if(a[l1] > b[l2]) ++l1,++l2;
else if(a[r1] > b[r2]) --r1,--r2;
else {
if(a[l1] == b[r2]) ++ans2;
else ans2 += 2;
++l1,--r2;
}
}
printf("%d %d\n", ans1, ans2);
return 0;
}