【POJ3190】Stall Reservations

            

problem

n头奶牛要在指定的时间内吃草,而一个机器只能同时给一个奶牛吃草。给你每头奶牛吃草的开始时间和结束时间,问你最小需要多少机器和每头牛对应的方案。 n<=5e4;

solution

按照开始吃草的时间将牛排序。
维护一个数组S,记录当前每个机器安排的最后一头牛。
对于每头牛,扫描S,找到一个满足的丢进去,如果没有就新建。

原始复杂度O(n^2),用一个小跟堆维护最后一头牛结束吃草的时间,即可优化到O(nlogn)。

codes

#include
#include
#include
using namespace std;
const int maxn = 50050;
struct cow{
    int l, r, id;
    bool operator < (const cow &b)const{
        return r>b.r;
    }
}a[maxn];  int belong[maxn];
bool cmp(cow a, cow b){ return a.l < b.l; }
priority_queueq;
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i].l>>a[i].r, a[i].id=i;
    sort(a+1, a+n+1, cmp);
    int ans = 1;  q.push(a[1]);  belong[a[1].id] = 1;
    for(int i = 2; i <= n; i++){
        if(!q.empty() && q.top().r < a[i].l){
            belong[a[i].id] = belong[q.top().id];
            q.pop();
            q.push(a[i]);
        }else{
            belong[a[i].id] = ++ans;
            q.push(a[i]);
        }
    }
    cout<'\n';
    for(int i = 1; i <= n; i++)
        cout<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像