湫湫系列故事——消灭兔子
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1883 Accepted Submission(s): 628
Problem Description
湫湫减肥
越减越肥!
最近,减肥失败的湫湫为发泄心中郁闷,在玩一个消灭免子的游戏。
游戏规则很简单,用箭杀死免子即可。
箭是一种消耗品,已知有M种不同类型的箭可以选择,并且每种箭都会对兔子造成伤害,对应的伤害值分别为Di(1 <= i <= M),每种箭需要一定的QQ币购买。
假设每种箭只能使用一次,每只免子也只能被射一次,请计算要消灭地图上的所有兔子最少需要的QQ币。
越减越肥!
最近,减肥失败的湫湫为发泄心中郁闷,在玩一个消灭免子的游戏。
游戏规则很简单,用箭杀死免子即可。
箭是一种消耗品,已知有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。
第一行有两个整数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
Source
Recommend
思路:贪心。
很简单的一个贪心,首先将兔子的血量按从大到小排,再将剑的伤害从大到小排。
然后优先队列。从兔子的最大值开始,然后找剑的伤害大于等于兔子血量的依次入队,队列是按价格升序排序的。
如过某个兔子没有剑能将它杀死,也就是队列为空的时候,也就无解。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<stdlib.h> 5 #include<iostream> 6 #include<queue> 7 using namespace std; 8 int cmp(const void*p,const void*q); 9 typedef struct pp 10 { 11 long long x; 12 long long y; 13 bool operator<(const pp&cx)const 14 { 15 return cx.y<y; 16 } 17 } ss; 18 ss a[100002]; 19 long long aa[100002]; 20 int main(void) 21 { 22 long long n,i,j,k,p,q; 23 long long N,M; 24 while(scanf("%lld %lld",&p,&q)!=EOF) 25 { 26 for(i=1; i<=p; i++) 27 { 28 scanf("%lld",&aa[i]); 29 } 30 sort(aa+1,aa+1+p); 31 for(i=0; i<q; i++) 32 { 33 scanf("%lld",&a[i].x); 34 } 35 for(i=0; i<q; i++) 36 { 37 scanf("%lld",&a[i].y); 38 } 39 qsort(a,q,sizeof(ss),cmp); 40 priority_queue<ss>que; 41 int cnt=0; 42 int z=q-1; 43 int flag=0; 44 long long sum=0; 45 for(i=p; i>0; i--) 46 { 47 for(j=z; j>=0; j--) 48 { 49 if(a[j].x>=aa[i]) 50 { 51 que.push(a[j]); 52 } 53 else break; 54 } 55 z=j; 56 if(que.empty()) 57 { 58 flag=1; 59 break; 60 } 61 else 62 { 63 ss kl=que.top(); 64 que.pop(); 65 if(kl.x<aa[i]) 66 { 67 flag=1; 68 break; 69 } 70 else 71 { 72 sum+=kl.y; 73 } 74 } 75 } 76 if(flag) 77 { 78 printf("No "); 79 } 80 else printf("%lld ",sum); 81 } 82 return 0; 83 } 84 85 int cmp(const void*p,const void*q) 86 { 87 ss*nn=(ss*)p; 88 ss*mm=(ss*)q; 89 return nn->x-mm->x; 90 }