注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1854][Scoi2010]游戏  

2014-10-20 22:56:04|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1854: [Scoi2010]游戏

做这道题的时候以为自己眼花了……

“咦我不是刚A了吗?”

然后仔细一看是2010年的题(居然又出了一道游戏- -

和上一道一样代码比较短

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int scan(){int i=0;scanf("%d",&i);return i;}
struct item{
int a,b;
item(){}
item(int aa,int bb):a(aa),b(bb){if(a > b)swap(a,b);}
}data[N];
int n;
bool v[(int)1e5+10];
bool operator < (item a,item b){if(a.a == b.a)return a.b < b.b;return a.a < b.a;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++){
a = scan();b = scan();
data[i] = item(a,b);
}
sort(data+1,data+1+n);
int top = 0;
for(i=1;i<=10000;i++){
while(data[top+1].a <= i&&top < n){
v[data[top+1].a]=1;
v[data[top+1].b]=1;
top++;
}
if(top < i || !v[i])break;
}
printf("%d\n",i-1);
return 0;
}

一开始觉得是网络流什么的……但是数据好大QAQ

然后想了一会……似乎是贪心?

题解:

考虑从小到大检查答案能不能为i

检查的方法是每次把最小属性小于等于i的所有装备都放到一个“包”里,如果满足包里的装备数>=i并且存在某个装备有一个属性为i,那么一定有合法方案。

正确性?我不太清楚,但是感觉没什么问题。

注意:

要判断包里的装备是否有属性为i的,我一开始写的时候忘了这个,差点WA掉= =、

  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017