51Nod 1191 消灭兔子 (贪心+优先队列)_shiyicode的博客-程序员秘密

技术标签: 算法刷题之旅  51Nod  贪心  优先队列  

题目链接消灭兔子

题目大意

n个兔子,每个兔子都有一个血量b[i]
m种箭(每种各一支),每种箭都有伤害值d[i]和价格p[i]
每个兔子只能被射一次,伤害值大于血量则死,每种箭只能用一次
问杀死所有兔子需要的最小价格为多少,若不能杀死,则No Solution
m,n小于50000)

思路

典型的贪心,每个兔子只能射一次,所以只能用伤害值大于其血量的箭,在此前提下,箭越便宜越好,故对兔子血量升序排列,箭对伤害值升序排列。
若i小于j 则第i支箭可以杀死的兔子,第j支箭也一定能杀死,而若j的价格小于i,就应该用j,所以用优先数列维护即可。

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
using namespace std;

const int N = 50009;
pair<int, int> p[N];
int b[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(m < n)
    {
        printf("No Solution\n");
        return 0;
    }
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<m;i++)
        scanf("%d%d",&p[i].first, &p[i].second);
    sort(b, b+n);
    sort(p, p+m);
    priority_queue<int> q;
    int i = 0, j = 0;
    long long ans = 0;
    while(j < m)
    {
        ans += p[j].second;
        q.push(p[j].second);
        if(p[j].first >= b[i] && i < n)
        {
            ++i;++j;
        }
        else
        {
            ans -= q.top();
            q.pop();
            ++j;
        }
    }
    if(i < n)
        printf("No Solution\n");
    else
        printf("%lld\n",ans);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/to_be_better/article/details/50352712

智能推荐

梦幻诛仙11职业linux架设手游,一款【梦幻诛仙11职业】手游端私服架设+JAVA后台+架设视频教程..._weixin_39860349的博客-程序员秘密

一款【梦幻诛仙11职业】手游端私服架设+JAVA后台+架设视频教程安装说明:最低配置2H4G安装CentOS 6.8体系封闭防火墙chkconfig iptables offservice iptables stop114 56 54安装浮图yum install -y wget &amp;&amp; wget -O install.sh http://download.bt.cn/install...

深入浅出Win32多线程程序设计-【1】基本概念_lzhdim的博客-程序员秘密

 &amp;#13;  引言&amp;#13;&amp;#13;  从单进程单线程到多进程多线程是操作系统发展的一种必然趋势,当年的DOS系统属于单任务操作系统,最优秀的程序员也只能通过驻留内存的方式实现所谓的&quot;多任务&quot;,而如今的Win32操作系统却可以一边听音乐,一边编程,一边打印文档。&amp;#13;&amp;#13;  理解多线程及其同步、互斥等通信方式是理解现代操作系统的关键一环,当我们精通了Win3...

视频直播的技术原理和实现思路方案整理_云豹科技官方的博客-程序员秘密

包括原理篇/思路篇/实践篇/方案篇/前端篇/总结原理篇何李石:七牛直播云服务技术详解直播模型及其实现一个通用的直播模型一般包括三个模块:主播方、服务器端和播放端。首先是主播方,它是产生视频流的源头,由一系列流程组成:第一,通过一定的设备来采集数据;第二,将采集的这些视频进行一系列的处理,比如水印、美颜和特效滤镜等处理;第三,将处理后的结果视频编码压缩成可观看可传输的视频流;第四,分发推流,即将压缩后的视频流通过网络通道传输出去。其次是播放端,播放端功能有两个层面,第一个层面是关键性的需求;另一

Mysql 报错:出现Table ‘performance_schema.session_status‘ doesn‘t [email protected]的博客-程序员秘密_performance_schema.session_status

在Centos下安装了mysql后,使用 数据库管理软件 HeidiSQL远程连接,报错:Table 'performance_schema.session_status' doesn't exist错误;解决办法1. 进入Mysql的安装目录的bin文件夹2. 打开cmd进入该目录执行mysql_upgrade -u root -p --force命令然后输入密码问题解决...

在Oracle中查询表的大小、表的占用情况和表空间的大小_hzp666的博客-程序员秘密

在Oracle中查询表的大小、表的占用情况和表空间的大小 有两种含义的表大小。一种是分配给一个表的物理空间数量,而不管空间是否被使用。可以这样查询获得字节数:select segment_name, bytes from user_segments where segment_type = 'TABLE'; 或者   Select Segment_Name,Sum(bytes)/...

程序员必背单词1_菜鸟腾飞的博客-程序员秘密_程序员必背单词

英语是程序员必备的一项技能,提高英语从单词开始,下面分享今天的单词 application 应用程式 应用、应用程序 application framework 应用程式框架、应用框架 应用程序框架 architecture 架构、系统架构 体系结构 argument 引数(传给函式的值)。叁见 parameter 叁数、实质叁数、实叁、自变量 array 阵列 数组 arrow ope

随便推点

CppSQLite - C++ Wrapper for SQLite_aperfels的博客-程序员秘密

原文地址:http://www.codeproject.com/Articles/6343/CppSQLite-C-Wrapper-for-SQLite/IntroductionThis article describes CppSQLite, a very thin C++ wrapper around the public domain SQLite datab

OAuth2实现单点登录SSO完整教程,其实不难!_程序员的成长之路的博客-程序员秘密

程序员的成长之路互联网/程序员/技术/资料共享关注阅读本文大概需要 13 分钟。来自:cnblogs.com/cjsblog/p/10548022.html前言技术这东西吧,看别人写的好...

MEGA-X 3D打印机教程: 04_建模、切片、打印_Mi_Story的博客-程序员秘密

时间:2021年3月9日22:10:38创作者:Microl创作类型:原创

URLSpan 字体颜色修改_沈纵情的博客-程序员秘密

SpannableString ss = new SpannableString( getString(R.string.tv_inkanet_protocol)); ss.setSpan(new URLSpan("inkanet.pateo.com.cn"), 0, getString(R.string.tv_inkanet_protocol).length(), S

(转) JS禁用鼠标滚轮事件_Dragon的记录的博客-程序员秘密_js禁止滚轮事件

function disabledMouseWheel() { if (document.addEventListener) { document.addEventListener('DOMMouseScroll', scrollFunc, false); }//W3C window.onmousewheel = document.onmousewheel =

全文检索系统与Lucene简介_weixin_33847182的博客-程序员秘密

一、什么是全文检索与全文检索系统?全文检索是指计算机索引程序通过扫描文章中的每一个词,对每一个词建立一个索引,指明该词在文章中出现的次数和位置,当用户查询时,检索程序就根据事先建立的索引进行查找,并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章中的每一...

推荐文章

热门文章

相关标签