腾讯马拉松复赛第三场,HDOJ-4544 - 湫湫系列故事——消灭兔子

     贪心+优先队列维护

     先将所有的兔子排序...再将所有的箭按伤害排序...

     做的时候从血量大的兔子往血量小的做...每次找能杀死这只兔子并且所需消耗最小的箭...

     直接做...超时..并且不好维护...引入优先队列...

Program:

#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include<stdio.h>
#define ll long long
#define oo 1000000000
using 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;
}