51nod 拉勾专业算法能力测评消灭兔子 优先队列+贪心
这道题一开始想了很久...还想着写网络流 发现根本不可能.... 然后就想着线段树维护然后二分什么的 最后发现优先队列就可以了 代码还是很简洁的啦 233
就是把兔子按血量从大到小排序一下然后➹箭按伤害从大到小也排序一下 然后每次找一只兔子 把能杀死他的箭全部丢到优先队列里 队首就是代价最小的啦 如果队列为空说明无解
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int M=50007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int b[M]; int n,m,ans,top=1; struct edge{int w,p;}e[M]; struct node{ int w,p; bool operator<(const node&x)const{return p>x.p;} }; bool cmp1(int a,int b){return a>b;} bool cmp2(edge a,edge b){return a.w>b.w;} priority_queue<node>q; int main() { n=read(); m=read(); for(int i=1;i<=n;i++) b[i]=read(); for(int i=1;i<=m;i++) e[i].w=read(),e[i].p=read(); sort(b+1,b+1+n,cmp1); sort(e+1,e+1+m,cmp2); for(int i=1;i<=n;i++){ while(e[top].w>=b[i]) q.push((node){e[top].w,e[top].p}),top++; if(q.empty()){printf("No Solution "); return 0;} node x=q.top(); q.pop(); ans+=x.p; } printf("%d ",ans); return 0; }