hdu 4544 优先队列+贪心

时间：2022-05-23 23:09:29

题意：最近，减肥失败的湫湫为发泄心中郁闷，在玩一个消灭免子的游戏。
游戏规则很简单，用箭杀死免子即可。
箭是一种消耗品，已知有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);

     }

 }

相关文章