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

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

百度之星 初赛第一轮 1001 超级赛亚人ACMer  

2015-05-31 10:09:00|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=600&pid=1001
题意及分析:
有n个人,m为初始战斗力,k为最大潜力提升上限。
将n个人的战斗力按升序排序,寻找匹配当前战斗力的敌人(即不超过最大战斗力但最接近)。然后加上k,继续匹配下一个,直到战胜所有敌人或者潜力提升上限被降为0(k=0)。最后判断能否战胜最大战斗力的敌人即可。属于贪心思想。
AC代码:
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
long long x[11000];
int m,k,n;
int getnext(int k1,long long k2){
    while (k1<=n&&x[k1]<=k2) k1++;
    return k1-1;
}
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) scanf("%I64d",&x[i]);
    sort(x+1,x+n+1);
    long long now=0,lim=m; int where=0;
    for (int i=k;i>=0;i--){
        int k1=getnext(where+1,lim);
        if (k1==n){printf("why am I so diao?\n"); return;}
        if (k1==where) {printf("madan!\n"); return;}
        where=k1; now=x[k1]; lim=now+i;
    }
    printf("madan!\n");
}
int main(){
    int t;
    scanf("%d",&t);
    for (int i=1;i<=t;i++){
        printf("Case #%d:\n",i); solve();
    }
    return 0;
}
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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