腾讯马拉松复赛第三场,HDOJ-4544 - 湫湫系列故事——消灭兔子
贪心+优先队列维护
先将所有的兔子排序...再将所有的箭按伤害排序...
做的时候从血量大的兔子往血量小的做...每次找能杀死这只兔子并且所需消耗最小的箭...
直接做...超时..并且不好维护...引入优先队列...
Program:
#include<iostream>#include<cmath>#include<stack>#include<queue>#include<set>#include<algorithm>#include<stdio.h>#define ll long long#define oo 1000000000using namespace std;struct node{ ll d,p; bool operator < (const node &x) const { return p>x.p; }}r[100005];ll n,m,b[100005];priority_queue<node> myqueue;bool cmp(node a,node b){ return a.d<b.d;}int main(){ ll i,h,ans; node p; while (~scanf("%I64d%I64d",&n,&m)) { for (i=1;i<=n;i++) scanf("%I64d",&b[i]); for (i=1;i<=m;i++) scanf("%I64d",&r[i].d); for (i=1;i<=m;i++) scanf("%I64d",&r[i].p); sort(b+1,b+1+n); sort(r+1,r+1+m,cmp); while (!myqueue.empty()) myqueue.pop(); h=m; ans=0; for (i=n;i>=1;i--) { while (h && r[h].d>=b[i]) myqueue.push(r[h]),h--; if (myqueue.empty()) { printf("No\n"); goto A; } p=myqueue.top(); myqueue.pop(); ans+=p.p; } printf("%I64d\n",ans); A: ; } return 0;}