hdu 4544 湫湫系列故事——消灭兔子(优先队列)
2024-08-29 14:45:33
题意:n只兔子(有血量),m只箭(有伤害、花费),每只兔子只能被射一次,求射死所有兔子的最少花费。
思路:贪心,2重循环,兔子从血量高到低,箭从伤害高到低,用能射死兔子的箭中花费最小的箭射。
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std; #define MAXN 100005 int B[MAXN];
struct Node{
int D,P;
}node[MAXN]; bool cmp(Node a,Node b){
return a.D<b.D;//升序
} struct cmp1{
bool operator ()(int &a,int &b){
return a>b;//最小值优先
}
}; priority_queue<int,vector<int>,cmp1>q;//最小值优先 int main(){
int n,m,i,j;
long long ans;
bool flag;
while(~scanf("%d%d",&n,&m)){
while(!q.empty())q.pop();
for(i=;i<n;++i)scanf("%d",&B[i]);
for(i=;i<m;++i)scanf("%d",&node[i].D);
for(i=;i<m;++i)scanf("%d",&node[i].P);
if(n>m){//别漏了。。
printf("No\n");
continue;
}
sort(B,B+n);
sort(node,node+m,cmp);
j=m-;
flag=true;
ans=;
for(i=n-;i>=;--i){
while(j>=&&node[j].D>=B[i]){
q.push(node[j].P);
--j;
}
if(q.empty()){
flag=false;
break;//有兔子杀不死
}
ans+=q.top();
q.pop();
}
if(flag)printf("%I64d\n",ans);
else printf("No\n");
}
return ;
}
最新文章
- ASP.NET AntiXSS的作用
- ThinkPHP 3.2.3 使用 Swift Mailer 邮件系统发送邮件
- React Native填坑之旅--class(番外篇)
- BSON 1.0版本规范(翻译)
- lstm的debug模式下编译不行貌似
- php Linux安装
- Delphi- 一些H8记录
- Django之路由系统
- WindowsPhone8中实现圆形图片的生成显示
- BZOJ 1483: [HNOI2009]梦幻布丁 [链表启发式合并]
- java思维导图
- 从0开始的Python学习001快速上手手册
- angular学习2
- SHELL-收集Oracle已应用的PSU信息
- FluentScheduler:开源轻量级定时任务调度架构
- http解析过程
- WISH开发API
- illegal multibyte sequence python3
- CodeForces 1073F Choosing Two Paths
- java实现word,ppt,excel,jpg转pdf
热门文章
- angular中多控制器的依赖注入写法
- HDU 4771 BFS + 状压
- vba功能语句
- WEB学习-基础知识:列表、表单、div和span、注释、字符实体、HTML废弃标签介绍
- CF 2018 Battle of Brains GYM 102062 F
- Codeforces 86D Powerful array (莫队算法)
- 数学知识巧学JCF(Java Collections framework)
- ZOJ - 4020 Traffic Light (BFS)
- springboot jetty替换tomcat
- dropwizard问题记录1:如何进行mvn package打包,如何在项目目录下运行