首页 > 代码库 > 51nod 1191 消灭兔子
51nod 1191 消灭兔子
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1191
有N只兔子,每只有一个血量B[i],需要用箭杀死免子。有M种不同类型的箭可以选择,每种箭对兔子的伤害值分别为D[i],价格为P[i](1 <= i <= M)。假设每种箭只能使用一次,每只免子也只能被射一次,计算要消灭地图上的所有兔子最少需要多少Q币。如不能杀死所有兔子,请输出No Solution。
特别说明:1、当箭的伤害值大于等于兔子的血量时,能将兔子杀死;2、血量B[i],箭的伤害值D[i],箭的价格P[i],均小于等于100000。
这个题很容易想到贪心,也就是每只兔子要被能够杀死它的价格最便宜且没有被用过的箭杀死,于是我们就可以先给兔子血量从大到小排个序,然后维护一个优先队列,存放能够杀死当前兔子的箭,每次取最便宜的即可(好像基本上百度上都是这个做法)
但是本垃圾的代码使用了线段树,线段树维护血量在这个区间的兔子有多少,然后按价格给箭排序,每只箭杀死它能够杀死的的兔子中血量最大的
1 #include<string> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdio> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 typedef long long ll; 11 const int MAXN=100005; 12 typedef struct node 13 { 14 int atk,cost; 15 node(){} 16 node(int a,int b){atk=a,cost=b;} 17 friend bool operator<(node a,node b){return a.cost<b.cost;} 18 }node ; 19 node arr[50005]; 20 int tree[400005]; 21 int query(int root,int l,int r,int val) 22 { 23 if(l==r)return l; 24 int mid=(l+r)/2; 25 if(val>=mid+1&&tree[root*2+2]>=1) 26 { 27 int tmp=query(root*2+2,mid+1,r,val); 28 if(tmp!=-1)return tmp; 29 } 30 if(tree[root*2+1]>=1)return query(root*2+1,l,mid,val); 31 return -1; 32 } 33 void changeval(int root,int l,int r,int pos,int val) 34 { 35 if(l==r) 36 { 37 tree[root]+=val; 38 return ; 39 } 40 int mid=(l+r)/2; 41 if(pos<=mid)changeval(root*2+1,l,mid,pos,val); 42 else changeval(root*2+2,mid+1,r,pos,val); 43 tree[root]=tree[root*2+1]+tree[root*2+2]; 44 } 45 int main() 46 { 47 int i,j; 48 int n,m; 49 scanf("%d%d",&n,&m); 50 if(n>m) 51 { 52 printf("No Solution\n"); 53 return 0; 54 } 55 memset(tree,0,sizeof(tree)); 56 for(i=0;i<n;i++) 57 { 58 int a; 59 scanf("%d",&a); 60 changeval(1,1,MAXN,a,1); 61 } 62 for(i=0;i<m;i++)scanf("%d%d",&arr[i].atk,&arr[i].cost); 63 sort(arr,arr+m); 64 ll sum=0; 65 int ans=0; 66 for(i=0;i<m;i++) 67 { 68 int pos=query(1,1,MAXN,arr[i].atk); 69 if(pos==-1)continue; 70 ans++; 71 sum+=arr[i].cost; 72 changeval(1,1,MAXN,pos,-1); 73 if(ans>=n)break; 74 } 75 if(ans<n) 76 { 77 printf("No Solution\n"); 78 } 79 else 80 { 81 printf("%lld\n",sum); 82 } 83 return 0; 84 } 85 86 /* 87 5 8 88 1 7 6 4 9 89 9 1 90 6 4 91 4 3 92 3 6 93 6 5 94 2 3 95 5 1 96 8 7 97 */
51nod 1191 消灭兔子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。