1034: [ZJOI2008]泡泡堂BNB


Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 3482  Solved: 1776
[Submit][Status][Discuss]

Description


  第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表
队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份
参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手,二号选手……,n号
选手捉对厮杀,共进行n场比赛。每胜一场比赛得2分,平一场得1分,输一场不得分。最终将双方的单场得分相加
得出总分,总分高的队伍晋级(总分相同抽签决定)。作为浙江队的领队,你已经在事先将各省所有选手的泡泡堂水
平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰
,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何
种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。当然你不想这样不
明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,浙江队最终分别能得到多少分。

Input


  输入的第一行为一个整数n,表示每支代表队的人数。接下来n行,每行一个整数,描述了n位浙江队的选手的
实力值。接下来n行,每行一个整数,描述了你的对手的n位选手的实力值。 20%的数据中,1<=n<=10; 40%的数
据中,1<=n<=100; 60%的数据中,1<=n<=1000; 100%的数据中,1<=n<=100000,且所有选手的实力值在0到100
00000之间。

Output


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

Sample Input



Sample Output


 
 

分析:


原本以为这道题是要让我们模拟泡泡堂orQQ堂(是不是还有偷包子模式23333)

好吧,读题一看,田鸡(忌)赛马问题。流传千古的贪心策略。。

田鸡赛马中用下等马去消耗齐威王上等马,从而保证我方上等马获胜。

这里同理:

1.如果我们当前的最慢马可以打败对方当前最慢马,直接打败它(因为可以多赢一局,没必要大材小用最后去用快马打败对方慢马)

2.如果我们当前最慢马不可以打败对方当前最慢马,且速度比它慢,那么它没有任何可以打赢的马,我们可以模仿田鸡的策略,浪费对面的快马(因为无论如何他都要失败,肯定浪费对面快马最优啊)

3.如果我们当前最慢马和对方当前最慢马速度相等,我们也要像策略2一样贪心,但我们则要讨论一下:

a.如果当前最快马可以打赢对面最快马。直接打败它(因为我们可以让对面最快马赢不了啊,如果我们用当前慢马去浪费对面快马,对面快马反而赢了)。

b.如果当前最快马不可以打赢对面最快马。那么模仿策略2贪心消耗对面快马。

再看看这道题:

求得分最大,和得分最小。得分最大模仿上面策略就好了,得分最小不就是对面得分最大吗(滑稽)。

AC代码:


# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
const int N = 1e5 + ;
int a[N],b[N],n;
int work(int my[],int his[]){
int myl,myr,hel,her,ans = ;
myl = hel = ;myr = her = n;
while(myl <= myr)
{
if(my[myl] < his[hel])
{
her--;myl++;
}
else if(my[myl] > his[hel])
{
ans += ;myl++;hel++;
}
else
{
if(my[myr] > his[her])
{
ans += ;myr--;her--;
}
else
{
if(my[myl] == his[her])
{
ans++;
}
myl++;her--;
}
}
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = ;i <= n;i++)
{
scanf("%d",&a[i]);
}
for(int j = ;j <= n;j++)
{
scanf("%d",&b[j]);
}
sort(a + ,a + n + );
sort(b + ,b + n + );
int Min = work(b,a);
int Max = work(a,b);
printf("%d %d\n",Max, * n - Min);
}

最新文章

  1. web兼容学习分析笔记-margin 和padding浏览器解析差异
  2. CI3.0控制器下面建文件夹 访问一直404 的解决方法
  3. SSM框架的整合思路&amp;功能实现
  4. CF459D Pashmak and Parmida&#39;s problem (树状数组)
  5. poj2488 bfs
  6. C#如何更好地理解引用类型和值类型
  7. HDU4916 Count on the path(树dp??)
  8. Codeforces Round #358 (Div. 2) D. Alyona and Strings 字符串dp
  9. ubuntu12.10+NDK r9 编译 ffmpeg 的一些参考资料Perhaps you should add the directory containing `libssl.pc&#39;
  10. HDU 4932 贪心
  11. hp惠普服务器监控硬盘
  12. jQuery.innerWidth() 函数详解
  13. Gulp实现服务器
  14. Cocos2d-x 3.0 编译出错 解决 error: expected &amp;#39;;&amp;#39; at end of member declaration
  15. TSP问题(旅行商问题)[分支限界法]
  16. MVC(3DOnLine)开发过程的一些难点以及知识点
  17. js上传图片
  18. Atitit html5.1 新特性attilax总结
  19. 时空KSOA之CS表单工具说明
  20. [转载]strtok函数和strtok_r函数

热门文章

  1. laravel之伪造跨站请求保护CSRF实现机制
  2. qt5.5.1+vs2010发送邮件
  3. 推荐一个有趣的Chrome扩展程序-查看任意网站的开发技术栈
  4. python的特殊数字类型(无穷大、无穷小等)
  5. df - 报告文件系统磁盘空间的使用情况
  6. nginx的编译安装
  7. docker环境安装
  8. SQA定义、质量模型、SQA与测试的关系
  9. js 根据指定个数切割数组
  10. 阿里云人脸比对API封装