hdu 4544 优先队列+贪心

题意:最近,减肥失败的湫湫为发泄心中郁闷,在玩一个消灭免子的游戏。
游戏规则很简单,用箭杀死免子即可。
箭是一种消耗品,已知有M种不同类型的箭可以选择,并且每种箭都会对兔子造成伤害,对应的伤害值分别为Di(1 <= i <= M),每种箭需要一定的QQ币购买。
假设每种箭只能使用一次,每只免子也只能被射一次,请计算要消灭地图上的所有兔子最少需要的QQ币。

链接:点我

贪心在能杀死某个兔子的箭里选择价格最小的

一开始直接两个for,tle,看了别人代码之后才知道用优先队列

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int b[MAXN],d[MAXN],p[MAXN];
int n,m,tt;
struct node
{
int d,p;
}a[MAXN];
bool cmp1(node a,node b)
{
return a.d>b.d;
}
struct cmp
{
bool operator()(int x,int y)
{
return x>y;
}
};
priority_queue<int,vector<int>,cmp > q;
bool vis[MAXN];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
while(!q.empty()) q.pop();
for(i=;i<n;i++) scanf("%d",&b[i]);
for(i=;i<m;i++) scanf("%d",&a[i].d);
for(i=;i<m;i++) scanf("%d",&a[i].p);
sort(b,b+n);
sort(a,a+m,cmp1);
long long ans=;
bool f=;
int t=;
for(i=n-;i>=;i--)
{
while(t<=m-&&a[t].d>=b[i])
{
q.push(a[t].p);
t++;
}
if(q.empty())
{
f=;
break;
}
ans+=q.top();
q.pop();
}
if(!f) printf("No\n");
else printf("%I64d\n",ans);
}
}
上一篇:iOS开发之创建颜色渐变视图View


下一篇:svg和css3创建环形渐变进度条