[BZOJ 1034] [ZJOI2008] 泡泡堂BNB 【贪心】
2024-08-27 10:20:49
题目链接: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;
}
最新文章
- wordpress源码解析-目录结构-文件调用关系(1)
- iOS中 项目开发易错知识点总结
- Sprint第二个冲刺(第六天)
- Ubuntu 装JDK
- [转]Android UI:看看Google官方自定义带旋转动画的ImageView-----RotateImageView怎么写(附 图片淡入淡出效果)
- 数学(动态规划,GCD):COGS 469. [NOI2010]能量采集
- 旅游[SPFA或是最小生成树][简单算法的灵活题]
- Yii Framework 的安装使用教程及文件结构详解
- c语言15行实现简易cat命令
- PHP常用的函数与小技巧
- day01_HTML
- PHP call_user_func
- poj 2689 (素数二次筛选)
- 关于code::blocks的编译速度问题
- asp.net 网页跳转的几种常用方法
- Android开发日常-listVIiew嵌套webView回显阅读位置
- 【DeepLearning】Exercise:Convolution and Pooling
- [转]VS2012正则查找
- Element ui 中使用table组件实现分页记忆选中
- 微信小程序 动态加载class