[bzoj 1034] [ZJOI2008]泡泡堂BNB

两支队伍各n人, 每人一个实力值, 两人一组单挑. 实力值x>y, x所在队得2分, y所在队不得分; x=y, 两队各得1分. 两队随机决定出场顺序, 问第一支队伍的最多和最少得分. (1≤n≤10^5, 实力值是[0,10^7]上的整数) 首先对两支队伍的实力值分别排序. 每场比赛会送出去2分, 因此, 求出一支队伍的最大得分, 也就求出了另一支队伍的最小得分. "田忌赛马" 的加强版. 发现可以建出点数, 边数均为线性的费用流, 然并卵......考虑了一下让对方从小到大出场, 我方尝试派出能打败对方的最弱选手. 如果不存在平局的情况, 这显然是正确的, 但是现在有平局, 试了两种策略都不对.

学习题解......

如果我方最弱选手能打败对方最弱选手, 那就打; 如果我方最强选手能打败对方最强选手, 那就打; 两种情况都不满足, 就让我方最弱打对方最强.

有点道理, 但我也不知道为什么 (所以这题白做了?)......在网上也没有找到. 如果阅读本文的您知道, 恳请告知, 感激不尽. QAQ

const int N = 1e5;

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

int solve(int* la, int* lb)
{
	int* ra = la+n-1, * rb = lb+n-1, ans = 0;
	
	while (ra-la >= 0) {
		if (*ra > *rb) ans += 2, --ra, --rb;
		else if (*la > *lb) ans += 2, ++la, ++lb;
		else ans += *la == *rb, ++la, --rb;
	}

	return ans;
}
	
int main()
{
	scanf("%d", &n);
	rep (i, 0, n) scanf("%d", a+i);
	rep (i, 0, n) scanf("%d", b+i);
	sort(a, a+n);
	sort(b, b+n);
	printf("%d %d\n", solve(a, b), 2*n - solve(b, a));
	return 0;
}