bzoj1034题解
2024-09-05 23:35:31
【解题思路】
广义田忌赛马的贪心模型。如果当前实力最差的马比对手实力最差的马强,则匹配;如果当前实力最强的马比对手实力最强的马强,亦匹配;若上述两点均不成立,拿己方最差的马去匹配对手最强的马。复杂度O(nlog2n)。
【参考代码】
#include <algorithm>
#include <cstdio>
#define REP(i,low,high) for(register int i=(low);i<=(high);++i)
#define __function__(type) __attribute__((optimize("-O2"))) inline type
#define __procedure__ __attribute__((optimize("-O2"))) inline void
using namespace std; __function__(int) score(const int&x,const int&y) {return x==y?:(x>y)*;} static int n; int a[],b[]; int main()
{
scanf("%d",&n); REP(i,,n) scanf("%d",a+i); REP(i,,n) scanf("%d",b+i);
sort(a+,a+n+),sort(b+,b+n+); int la=,ra=n,lb=,rb=n,ans=;
while(la<=ra)
{
if(a[la]>b[lb]) {ans+=score(a[la++],b[lb++]); continue;}
if(a[ra]>b[rb]) {ans+=score(a[ra--],b[rb--]); continue;}
ans+=score(a[la++],b[rb--]);
}
printf("%d ",ans),la=,ra=n,lb=,rb=n,ans=;
while(la<=ra)
{
if(a[la]<b[lb]) {ans+=score(a[la++],b[lb++]); continue;}
if(a[ra]<b[rb]) {ans+=score(a[ra--],b[rb--]); continue;}
ans+=score(a[ra--],b[lb++]);
}
return printf("%d\n",ans),;
}
最新文章
- nodejs复习04
- test spring in category
- linux学习8 第八章 权限管理
- Windows Azure Web Site (14) Azure Web Site IP白名单
- 二进制流 最后一段数据是最后一次读取的byte数组没填满造成的
- JQuery基础教程:事件(下)
- excel VLOOKUP函数的用法
- ASP.NET服务器控件OnClientClick事件中Eval()作为js方法的参数的一种写法
- 2014-02-27WPF学习笔记
- iOS开发 autoResizingMask使用
- poj 2488A Knight&#39;s Journey
- rac 10g 加入节点具体解释
- mysql主键设置成auto_increment时,进行并发性能測试出现主键反复Duplicate entry &;#39;xxx&;#39; for key &;#39;PRIMARY&;#39;
- 【Sort】HeapSort
- speedment 入门教程
- 小子给大家分享一个或者多个新手创建tableview经常会遇到的坑(动态创建控件,xib的重用)
- new function
- New UWP Community Toolkit - RadialGauge
- JDK安装:CentOS和Windows环境
- flask 异步发送邮件