腾讯马拉松复赛第三场,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;}

1楼acm7913小时前

话说我跟楼主的思路是一样的，但是还是赤裸裸的t了。估计是自己写挫了吧。

Re: kk3033小时前

回复acm79n话说我用C++交T...用G++交300ms~