[bzoj] 1034: [ZJOI2008]泡泡堂BNB

发表于   |   分类于   |  

题意

传送门

分析

与”田忌赛马”类似.
最弱或最强能赢则赢,不能赢则最弱打对方最强

代码

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
52
#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>

#define  maxn  100010LL

int n ;
int a[maxn] , b[maxn] ;

int calc(int* a , int* b) {
trueint ret = 0 , l1 , l2 , r1 , r2 ;
truel1 = l2 = 1 , r1 = r2 = n ;
truewhile (l1 <= r1)
true    if (a[l1] > b[l2]) ret += 2 , l1 ++ , l2 ++ ;
true    else if (a[r1] > b[r2]) ret += 2 , r1 -- , r2 -- ;
true    else ret += (a[l1]==b[r2]) , l1 ++ , r2 -- ;
truereturn ret ;
}

int main() {
int i ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
truefor (i = 1 ; i <= n ; i ++ ) read(a[i]) ;
truefor (i = 1 ; i <= n ; i ++ ) read(b[i]) ;
truestd::sort(a+1 , a+n+1) ;
truestd::sort(b+1 , b+n+1) ;
trueprintf("%d %d\n", calc(a , b) , 2*n-calc(b , a)) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章