[BZOJ 1034] [ZJOI2008] 泡泡堂BNB 【贪心】

题目链接:BZOJ - 1034

题目分析

这道题和田忌赛马的典故很相似。

先要将两队的队员都按照水平从小到大分别排序。

然后每次尝试用我方最弱的队员赢对方最弱的队员,或者用我方最强的队员赢对方最强的队员。

如果都不行,就用我方最弱的队员对抗对方最强的队员。

这样求出的就是我方的最高分。

由于进行 n 轮比赛之后,双方的比分和为 2n ,所以我方的最低分就是 2n - 对方的最高分。

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath> using namespace std; const int MaxN = 100000 + 5; int n, Min, Max, Ans;
int A[MaxN], B[MaxN]; inline void Cmp(int x, int y)
{
if (x > y) Ans += 2;
if (x == y) Ans += 1;
} int Solve(int *A, int *B)
{
Ans = 0;
int l1, r1, l2, r2;
l1 = l2 = 1;
r1 = r2 = n;
while (l1 <= r1)
{
if (A[l1] > B[l2]) Cmp(A[l1++], B[l2++]);
else if (A[r1] > B[r2]) Cmp(A[r1--], B[r2--]);
else Cmp(A[l1++], B[r2--]);
}
return Ans;
} int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &B[i]);
sort(A + 1, A + n + 1);
sort(B + 1, B + n + 1);
printf("%d %d\n", Solve(A, B), 2 * n - Solve(B, A));
return 0;
}

  

上一篇:mysql where 1=1和 1=0 的作用


下一篇:Hadoop学习------Hadoop安装方式之(一):单机部署