湫湫系列故事——消灭兔子

湫湫减肥
　　越减越肥！
　　
　　最近，减肥失败的湫湫为发泄心中郁闷，在玩一个消灭免子的游戏。
　　游戏规则很简单，用箭杀死免子即可。
　　箭是一种消耗品，已知有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

题意：用更少的Q币吧所有的兔子都杀死。

思路：最大的兔子先杀死，选伤害足够花费最小的箭，依次类推，这样就是一个最优解。（自己可以证明）

 

#include<iostream> #include<algorithm> #include<queue> #include<cstdio> using namespace std; const int max_n=100005; int n,m,b[max_n],d[max_n],p[max_n]; long long int sumCost; struct Node{int hurt;int cost;bool operator<(Node b)const{return cost>b.cost;} }arrow[max_n],nowNode; bool cmp(Node a,Node b) {return a.hurt>b.hurt; } int main() {while(scanf("%d%d",&n,&m)!=EOF){priority_queue<Node>q;sumCost=0;for(int i=0;i<n;i++){scanf("%d",&b[i]);}for(int i=0;i<m;i++){scanf("%d",&d[i]);}for(int i=0;i<m;i++){scanf("%d",&p[i]);}sort(b,b+n,greater<int>()); //按血量从大到小排序 for(int i=0;i<m;i++){arrow[i].hurt=d[i];arrow[i].cost=p[i];}sort(arrow,arrow+m,cmp); //按箭的伤害从大到小排序 bool flag=true;int right=0;for(int i=0;i<n;i++){while(right<m&&arrow[right].hurt>=b[i]){q.push(arrow[right]);right++;}if(q.empty()){cout<<"No"<<endl;flag=false;break;}nowNode=q.top();q.pop();sumCost+=nowNode.cost;} if(flag)printf("%lld\n",sumCost);}return 0; }

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的湫湫系列故事——消灭兔子的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。