首页 > 代码库 > hdu 4544 湫湫系列故事——消灭兔子 优先队列+贪心
hdu 4544 湫湫系列故事——消灭兔子 优先队列+贪心
将兔子的血量从小到大排序,箭的威力也从小到大排序,
对于每只兔子将威力大于血量的箭加入队列,写个优先队列使得出来数位价钱最少。。
#include<stdio.h> #include<queue> #include<algorithm> #include<iostream> #include<functional> using namespace std; const int maxn=100010; struct tt { int d; int p; bool operator<(const tt&t) const{ return d>t.d||(d==t.d&&p<t.p); } } pt[maxn]; int b[maxn]; priority_queue<int , vector<int> , greater<int> > q; int main() { int n,m,i,j; while(~scanf("%d%d",&n,&m)) { for(i=1;i<=n;i++) scanf("%d",&b[i]); for(i=1;i<=m;i++) scanf("%d",&pt[i].d); for(i=1;i<=m;i++) scanf("%d",&pt[i].p); sort(b+1,b+1+n,greater<int>()); sort(pt+1,pt+1+m); while(!q.empty()) q.pop(); __int64 ans=0; bool flag=1; for(i=1,j=1;i<=n;i++) { while(j<=m&&pt[j].d>=b[i]) { q.push(pt[j].p); j++; } if(!q.empty()) { ans=ans+q.top(); q.pop(); } else { flag=0; break; } } if(flag) printf("%I64d\n",ans); else printf("No\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。