hdu 4544 湫湫系列故事——消灭兔子（优先队列）

题意：n只兔子（有血量），m只箭（有伤害、花费），每只兔子只能被射一次，求射死所有兔子的最少花费。

思路：贪心，2重循环，兔子从血量高到低，箭从伤害高到低，用能射死兔子的箭中花费最小的箭射。

#include<iostream>

#include<stdio.h>

#include<queue>

#include<algorithm>

using namespace std;

#define MAXN 100005

int B[MAXN];

struct Node{

    int D,P;

}node[MAXN];

bool cmp(Node a,Node b){

    return a.D<b.D;//升序

}

struct cmp1{

    bool operator ()(int &a,int &b){

        return a>b;//最小值优先

    }

};

priority_queue<int,vector<int>,cmp1>q;//最小值优先

int main(){

    int n,m,i,j;

    long long ans;

    bool flag;

    while(~scanf("%d%d",&n,&m)){

        while(!q.empty())q.pop();

        for(i=;i<n;++i)scanf("%d",&B[i]);

        for(i=;i<m;++i)scanf("%d",&node[i].D);

        for(i=;i<m;++i)scanf("%d",&node[i].P);

        if(n>m){//别漏了。。

            printf("No\n");

            continue;

        }

        sort(B,B+n);

        sort(node,node+m,cmp);

        j=m-;

        flag=true;

        ans=;

        for(i=n-;i>=;--i){

            while(j>=&&node[j].D>=B[i]){

                q.push(node[j].P);

                --j;

            }

            if(q.empty()){

                flag=false;

                break;//有兔子杀不死

            }

            ans+=q.top();

            q.pop();

        }

        if(flag)printf("%I64d\n",ans);

        else printf("No\n");

    }

    return ;

}