POJ-3190 Stall Reservations---优先队列+贪心

题目链接：

题目大意：

有N头奶牛，每头奶牛都会在[1,1000000]的时间区间内的子区间进行挤奶。挤奶的时候奶牛一定要单独放在一个牛棚中。一头奶牛的结束时间与另一头奶牛的开始时间重合的时候2头奶牛不能放在同一个牛棚中，例A牛时间[5,10]，B牛时间[10,12]，那么需要用2个牛棚放这2头牛。输入N头牛的所有的挤奶时间区间，要求输出最少要建几个牛棚，以及每头牛挤奶的时候在第几号牛棚。

思路：

将奶牛根据挤奶开始时间排序后，从第一只奶牛进行考虑。从牛棚的优先队列中返回结束时间最短的牛棚，看该奶牛是否能放在该牛棚中。如果能，就更新该牛棚的结束时间，更新为该奶牛的开始时间；如果不能，就新创建一个牛棚，并将奶牛放在这个牛棚中。重复以上，直到所有奶牛都被放完。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 typedef pair<int, int> Pair ;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 int T, n, m, cases;

 struct node

 {

     int x, y, id;

     bool operator <(const node a)const

     {

         return y > a.y;

     }

 };

 bool cmp(node a, node b)

 {

     return a.x < b.x || a.x == b.x && a.y < b.y;

 }

 node a[maxn];

 int id[maxn];

 int main()

 {

     cin >> n;

     for(int i = ; i <= n; i++)

     {

         scanf("%d%d", &a[i].x, &a[i].y);

         a[i].id = i;

     }

     sort(a + , a + n + , cmp);

     priority_queue<node>q;

     int ans = ;

     id[a[].id] = ;

     q.push(a[]);

     for(int i = ; i <= n; i++)

     {

         node now = q.top();

         if(a[i].x > now.y)

         {

             q.pop();

             id[a[i].id] = id[now.id];

             q.push(a[i]);

         }

         else

         {

             id[a[i].id] = ++ans;

             q.push(a[i]);

         }

     }

     cout<<ans<<endl;

     for(int i = ; i <= n; i++)cout<<id[i]<<endl;

     return ;

 }

巴特西

POJ-3190 Stall Reservations---优先队列+贪心

最新文章

热门文章