HDU4544 湫湫系列故事――消灭兔子
系列 故事 兔子 消灭
2023-09-27 14:23:51 时间
Tags: 数据结构,贪心
Analysis:
将兔子的血量从大到小排序,将箭的杀伤力从大到小排序,对于每一个兔子血量,
将比他大的杀伤力大的剑压入优先队列,优先队列自己重写,让它每次抛出的数为价钱最小。
Code:
#include <cstdio> #include <queue> #include <algorithm> #include <functional> using namespace std; typedef long long LL; const int maxn = 100010; struct tt { int d; int p; bool operator <(const tt& t) const { return d>t.d||(d==t.d&&p<t.p); } } pt[maxn]; int b[maxn]; priority_queue<int , vector<int>, greater<int> > 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<int>()); sort(pt+1,pt+1+m); while(!q.empty()) q.pop(); LL 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 += q.top(); q.pop(); } else { flag = 0; break; } } if(flag) printf("%I64d\n",ans); else printf("No\n"); } return 0; }
相关文章
- 【opencv 系列】第3章 图像的8种变换
- 【Vue 快速入门系列】一文透彻vue中使用axios及跨域问题的解决
- 【Vue 快速入门系列】ref、props、mixin、插件使用、样式混合解决方案合集
- 温故js系列(16)-数组&数组方法使用详解
- HDU 4540 威威猫系列故事——打地鼠 (状态压缩DP)
- 2013腾讯编程马拉松初赛第二场(3月22日) 小Q系列故事——为什么时光不能倒流 ---好水!!
- hdu4501——小明系列故事——买年货(多维背包)
- Web 前端开发精华文章集锦(jQuery、HTML5、CSS3)【系列十八】
- 计算机视觉系列-轻松掌握 MMDetection 中常用算法:CenterNet
- Flink大数据实时计算系列-Flink的Keyed State之过期超时策略
- SpringBoot系列十:SpringBoot整合Redis
- Spring Boot2 系列教程(四)理解Spring Boot 配置文件 application.properties
- SpringBoot2.x系列教程(五十九)SpringBoot实现国际化i18n功能
- SpringBoot2.x系列教程(四十九)Spring Boot中JdbcTemplate源码分析
- SpringBoot2.x系列教程(三十八)SpringBoot配置Https访问
- RocketMQ系列实战
- boost.asio系列——io_service