51nod 1191(贪心+优先队列)-蒲公英云

51nod 1191(贪心+优先队列)

怼烎@ 2022-07-27 13:39 284阅读 0赞

有N只兔子，每只有一个血量B[i]，需要用箭杀死免子。有M种不同类型的箭可以选择，每种箭对兔子的伤害值分别为D[i]，价格为P[i](1 <= i <= M)。假设每种箭只能使用一次，每只免子也只能被射一次，计算要消灭地图上的所有兔子最少需要多少Q币。如不能杀死所有兔子，请输出No Solution。

特别说明：1、当箭的伤害值大于等于兔子的血量时，能将兔子杀死；2、血量B[i]，箭的伤害值D[i]，箭的价格P[i]，均小于等于100000。

分析：

贪心+优先队列。

将兔子排序之后在将弓箭按伤害值排序，之后从大到小枚举兔子，然后从伤害值大到小枚举弓箭，伤害值大于等于当前兔子的弓箭入优先队列，优先队列里面花费小优先，这样将所有满足伤害值大于等于当前兔子的弓箭都入队列之后就可以直接取队首元素去杀掉当前兔子，删除队首元素，然后继续这一过程就可以了，知道兔子枚举完或者队列为空。

#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define inf 100000005
int const maxn = 50005;
int b[maxn];
struct node
{
    int d,p;
    node(int d = 0 , int p = 0):d(d),p(p){};
    bool operator < (const node &u)const
    {
        if(p!=u.p)return u.p<p;//p小优先
        return d>u.d;
    }
}A[maxn];
bool cmp(node a,node b)
{
    if(a.d!=b.d)return a.d<b.d;  //伤害值从小到大
    return a.p<b.p;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i = 0 ; i < m ; i++)
        {
            scanf("%d%d",&A[i].d,&A[i].p);
        }
        sort(b,b+n);
        sort(A,A+m,cmp);
        long long ans = 0 ;
        priority_queue<node> q ;
        int j = n-1 ;
        int i = m-1 ;
        while(j>=0)
        {
            if(i>=0&&A[i].d>=b[j])
            {
                q.push(A[i]);
                i--;
            }
            else
            {
                j--;
                if(q.empty()){break;}
                else {ans+=q.top().p;q.pop();}
            }
        }
        if(j<0)
        {
            printf("%I64d\n",ans);
        }
        else puts("No Solution");
    }
    return 0 ;
}