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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3709][PA2014]Bohater  

2014-09-13 14:24:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3709: [PA2014]Bohater

比较水的题

但是因为我傻逼所以对拍了一中午才A

对拍还要写spj好蛋疼啊!

按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+100;
int n,m;
long long scan(){
char cc=' ';long long re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return fh*re;
}
struct food{
int lim,add,id;
food(){}
food(int l,int a,int i):lim(l),add(a),id(i){}
}ene[N],eat[N],list[N];
bool cmp(food a,food b){return a.lim < b.lim;}
int en,enn,ans[N],ln,lin[N];
int main(){
int i,j,a,b;
long long hp,last=0;
//freopen("input.txt","r",stdin);
n=scan();hp = scan();
for(i=1;i<=n;i++){
a = scan();b = scan();
b -= a;
if(b>0)eat[++en] = food(a,b,i);
else if(b == 0) list[++ln] = food(a,b,i);
else ene[++enn] = food(a+b,-b,i),last += b;
}
sort(eat+1,eat+1+en,cmp);
for(i=1;i<=en;i++){
if(hp<=eat[i].lim){printf("NIE\n");return 0;}
hp+=eat[i].add;
ans[++ans[0]] = eat[i].id;
}
for(i=1;i<=ln;i++){
if(hp<=list[i].lim){printf("NIE\n");return 0;}
ans[++ans[0]] = list[i].id;
}
lin[0]=0;
hp += last;
sort(ene+1,ene+1+enn,cmp);
for(i=1;i<=enn;i++){
if(hp<=ene[i].lim){printf("NIE\n");return 0;}
hp+=ene[i].add;
lin[++lin[0]] = ene[i].id;
}
for(i=lin[0];i;i--)ans[++ans[0]] = lin[i];
printf("TAK\n");
for(i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}

题解:
相当于每个Monster有两个值,一个是打败所需的血量a,另一个是打败后自己血量的改变值b
对于b值大于0的Monster,你可以把它看做蛋糕,吃蛋糕有一个限制,吃完之后可以加血
所以明显可以对于限制从小到大排序一个一个吃
然后再吃(打)改变量为0的Monster
最后对于b<0的有点蛋疼,似乎怎么搞都不太对
但是如果反过来思考,先把血量全减掉然后时间倒流
你会发现……又变成了前面的吃蛋糕问题!
细节:
其实算不上细节……
只是我比较傻逼所以b=0的时候忘记判断有没有达到限制,所以WA出翔
  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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