湫湫系列故事——消灭兔子 hdu4544 贪心

2024-03-27 02:40

本文主要是介绍湫湫系列故事——消灭兔子 hdu4544 贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

湫湫减肥 
  越减越肥! 
   
  最近,减肥失败的湫湫为发泄心中郁闷,在玩一个消灭免子的游戏。 
  游戏规则很简单,用箭杀死免子即可。 
  箭是一种消耗品,已知有M种不同类型的箭可以选择,并且每种箭都会对兔子造成伤害,对应的伤害值分别为Di(1 <= i <= M),每种箭需要一定的QQ币购买。 
  假设每种箭只能使用一次,每只免子也只能被射一次,请计算要消灭地图上的所有兔子最少需要的QQ币。 

Input

输入数据有多组,每组数据有四行; 
第一行有两个整数N,M(1 <= N, M <= 100000),分别表示兔子的个数和箭的种类; 
第二行有N个正整数,分别表示兔子的血量Bi(1 <= i <= N); 
第三行有M个正整数,表示每把箭所能造成的伤害值Di(1 <= i <= M); 
第四行有M个正整数,表示每把箭需要花费的QQ币Pi(1 <= i <= M)。 

特别说明: 
1、当箭的伤害值大于等于兔子的血量时,就能将兔子杀死; 
2、血量Bi,箭的伤害值Di,箭的价格Pi,均小于等于100000。

Output

如果不能杀死所有兔子,请输出”No”,否则,请输出最少的QQ币数,每组输出一行。

Sample Input

3 3
1 2 3
2 3 4
1 2 3
3 4
1 2 3
1 2 3 4
1 2 3 1

Sample Output

6
4

忘记换方向了 将就着看吧

注释过的是朴素算法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;struct Arrow
{int di;int pi;friend bool operator<(Arrow a,Arrow b){return a.pi>b.pi;}
}arrow[100010];int rabit[100010];
//int visit[100010];bool cmp(Arrow a,Arrow b)
{//if(a.pi!=b.pi) return a.pi<b.pi;return a.di>b.di;
}bool cmp1(int a,int b)
{return a>b;
}int main()
{int n,m;while(cin>>n>>m){/*if(n>m) {cout<<"No"<<endl;continue;}*///else//{priority_queue<Arrow> que;memset(rabit,0,sizeof(rabit));//memset(visit,0,sizeof(visit));for(int i=0;i<n;i++){scanf("%d",&rabit[i]);}for(int i=0;i<m;i++){scanf("%d",&arrow[i].di);}for(int i=0;i<m;i++){scanf("%d",&arrow[i].pi);}sort(rabit,rabit+n,cmp1);sort(arrow,arrow+m,cmp);int j=0,flag=0;long long qbit=0;for(int i=0;i<n;i++){while(j<m&&arrow[j].di>=rabit[i]){que.push(arrow[j]);j++;}if(que.empty()){flag=1;break;}else{qbit+=que.top().pi;que.pop();}/*for(j=0;j<m;j++){if(arrow[j].di>=rabit[i]&&visit[j]==0){qbit+=arrow[j].pi;//cout<<"add"<<arrow[j].pi<<endl;visit[j]=true;break;}}*/}if(flag) cout<<"No"<<endl;else cout<<qbit<<endl;//}}return 0;
}

 

这篇关于湫湫系列故事——消灭兔子 hdu4544 贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/850691

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

ural 1820. Ural Steaks 贪心

1820. Ural Steaks Time limit: 0.5 second Memory limit: 64 MB After the personal contest, happy but hungry programmers dropped into the restaurant “Ural Steaks” and ordered  n specialty steaks

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu