poj 3190 贪心 + 优先队列优化

本文主要是介绍poj 3190 贪心 + 优先队列优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对cow进行排列。按L以及R从小到大排序。确保遍历的时候优先取到最小的L.

然后就可以对cow遍历求解。

#include <iostream>
#include <queue>
#include <algorithm>
#include<functional>
using namespace std;
struct N
{int l,r,id,stall;bool operator <(const N &a)const{return a.r<r;}
}cow[50010];
bool cmp(N &a,N &b)
{return a.l<b.l;
}
int main()
{priority_queue<N>que;int n;cin>>n;for(int i=1;i<=n;i++){cin>>cow[i].l>>cow[i].r;cow[i].id=i;}sort(cow+1,cow+n+1,cmp);cow[0].stall=1;cow[0].r=0;que.push(cow[0]);int a[50010];int S=2;for(int i=1;i<=n;i++){N c=que.top();if(cow[i].l>c.r){que.pop();cow[i].stall=c.stall;a[cow[i].id]=c.stall;que.push(cow[i]);}else{cow[i].stall=S;a[cow[i].id]=S++;que.push(cow[i]);}}cout<<S-1<<endl;for(int i=1;i<=n;i++)cout<<a[i]<<endl;return 0;
}

这篇关于poj 3190 贪心 + 优先队列优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---