4144:畜栏保留问题 查看提交统计提示提问 总时间限制: 1000ms 内存限制: 65536kB 描述 农场有N头牛，每头牛会在一个特定的时间区间[A, B]（包括A和B）在畜栏里挤奶，且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求，并要求给出每头牛被安排的方案。对于多种可行方案，主要输出一种即可。
输入 输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行每行包含两个数，分别表示这头牛的挤奶时间[Ai, Bi](1 ≤ A≤ B ≤ 1, 000, 000)。 输出 输出的第一行包含一个整数，表示最少需要的畜栏数；接下来N行，第i+1行描述了第i头牛所被分配的畜栏编号（从1开始）。 样例输入 5 1 10 2 4 3 6 5 8 4 7 样例输出 4 1 2 3 2 4 来源 http://poj.org/problem?id=3190
/* 4144:畜栏保留问题 思路，利用有限队列记录畜栏的结束时间，将每一头奶牛与队列中结束时间最早的畜栏 相比较，如果奶牛开始时间大于（不等于）畜栏结束时间则将该畜栏分配给这只奶牛， 并修改畜栏结束时间为奶牛的结束时间，若不存在该畜栏，则重新添加一个畜栏，并将 结束时间修改为奶牛结束时间 注意，重载opretator < ()const 中间的空格要加上 */ #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; struct Cow{ int a,b; //开始结束时间 int NO; //奶牛编号 //按开始时间从小到大排序 bool operator < (const Cow & c)const{ return a < c.a; } }cows[50100]; int pos[50100]; struct Stall{ int end; //结束时间 int NO; //使在实现优先队列时结束时间短的优先级高 bool operator< (const Stall &s) const { return end > s.end; } Stall(int e,int n):end(e),NO(n){ } }; int main() { int n; cin >> n; for(int i = 0;i < n;++i){ cin >> cows[i].a >> cows[i].b; cows[i].NO = i; } sort(cows,cows + n); int total = 0; priority_queue<Stall> pq; for(int i = 0;i < n;++i){ if(pq.empty()){ total++; pq.push(Stall(cows[i].b,total)); pos[cows[i].NO] = total; } else{ Stall st = pq.top(); if(st.end < cows[i].a){ pq.pop(); pos[cows[i].NO] = st.NO; pq.push(Stall(cows[i].b,st.NO)); } else{ ++total; pq.push(Stall(cows[i].b,total)); pos[cows[i].NO] = total; } } } cout << total << endl; for(int i = 0;i < n;++i){ cout << pos[i] << endl; } return 0; }