设为首页 加入收藏

TOP

hdu 4544 湫湫系列故事――消灭兔子 优先队列+贪心
2015-07-20 18:07:19 来源: 作者: 【 】 浏览:5
Tags:hdu 4544 系列 故事 消灭 兔子 优先 队列 贪心

将兔子的血量从小到大排序,箭的威力也从小到大排序,

对于每只兔子将威力大于血量的箭加入队列,写个优先队列使得出来数位价钱最少。。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; const int maxn=100010; struct tt { int d; int p; bool operator<(const tt&t) const{ return d>t.d||(d==t.d&&p
       
         , greater
        
          > q; int main() { int n,m,i,j; while(~scanf("%d%d",&n,&m)) { for(i=1;i<=n;i++) scanf("%d",&b[i]); for(i=1;i<=m;i++) scanf("%d",&pt[i].d); for(i=1;i<=m;i++) scanf("%d",&pt[i].p); sort(b+1,b+1+n,greater
         
          ()); sort(pt+1,pt+1+m); while(!q.empty()) q.pop(); __int64 ans=0; bool flag=1; for(i=1,j=1;i<=n;i++) { while(j<=m&&pt[j].d>=b[i]) { q.push(pt[j].p); j++; } if(!q.empty()) { ans=ans+q.top(); q.pop(); } else { flag=0; break; } } if(flag) printf("%I64d\n",ans); else printf("No\n"); } return 0; }
         
        
       
      
     
    
   
  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇wikioi 1051哈希表 下一篇HDU 1272: 小希的迷宫(并查集)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: