POJ-2376 Cleaning Shifts---区间覆盖&贪心

题目链接：

题目大意：

farmer John要安排他的牛清理牛棚，一共有T个牛棚要清理，每头牛可以清理相邻的牛棚。比如，一头牛可以清理4-7号牛棚。当然了，牛清理的牛棚可以重叠。现在要你求出可以完成牛棚的清理的最少头牛的个数，不可以就输出-1.

思路：

贪心题。题目意思很明显是求最少的区间覆盖掉大区间。先对这些时间段排好序(见代码)，这个排序应该是没什么问题的。然后呢，第一头牛肯定要选，就从这头牛开始，选取下一头牛。下一头牛怎么选取呢？即在满足条件的牛里面（注意：满足条件的牛是只要开始工作时间 start>=cow[0].y+1 即可），选取右边界值最大的那个，因为这样子能够覆盖掉最多的时间段。以此类推，故贪心法求之。

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 int n, t;

 struct node

 {

     int l ,r;

     bool operator < (const node a)const

     {

         return l < a.l || l == a.l && r > a.r;

     }

 };

 node a[];

 int main()

 {

     while(scanf("%d%d", &n, &t) != EOF)

     {

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

         {

             scanf("%d%d", &a[i].l, &a[i].r);

         }

         sort(a, a + n);

         int ans = , end = , now = ;

         while(end < t)

         {

             int begin = end + ;

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

             {

                 if(a[i].l <= begin)//要覆盖起点

                 {

                     end = max(end, a[i].r);//取最远的终点

                 }

                 else

                 {

                     now = i;//不能覆盖起点，说明之后的都不可以，直接跳出，记录下标

                     break;

                 }

             }

             if(end < begin)//没找到牛，直接跳出

             {

                 ans = -;

                 break;

             }

             else ans++;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

POJ-2376 Cleaning Shifts---区间覆盖&贪心

最新文章

热门文章