【贪心】POJ2376-Cleaning Shifts

【题目大意】

给出几个小区间和大区间，求覆盖整个大区间的最少小区间个数，如果不可能则输出-1。

【思路】

这道程序写得我很不爽快，迷迷糊糊写完了，提交一遍AC了，可是我自己都没怎么弄懂到底是怎么写出来的（我果然不是很擅长贪心的实现）。思路很简单，显而易见地贪心，关键在于如何实现这个思路。

先以区间左边界为关键字进行排序，每次选左边界能与上一个右边界相接的区间中右边界最大的那一个。我的实现方法是这样的：假设当前已经覆盖区域的右边界为lright，之前能覆盖到的最大右边界为p，ans为需要的小区间数。对于每一个小区间：

（1）如果它的左边界已经大于lright+1，即p已经是能与上一个右边界相接的区间中右边界最大的那一个，将lright更新为p，p初始化为-1，ans+1；当然，如果p本身就是-1，说明无法与已覆盖区域连接，无解（当然无解的情况并不仅限于这一种，还有可能是无法覆盖到大区间的右边界等），可以直接退出循环。

（2）如果当前左边界小于等于lright+1，且右边界大于等于lright+1，在当前右边界和p中选取较大的一个；如果p恰好大于等于大区间的右边界，ans+1，退出循环。

要注意的一点事，所谓衔接不是[0,1][1,2]这样首尾相接，而是[0,1][2,3]即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int MAXN=+;

 struct interval

 {

     int left,right;

     bool operator < (const interval &x) const

     {

         return (left<x.left);

     }

 };

 int n,t;

 interval cow[MAXN];

 int main()

 {

     scanf("%d%d",&n,&t);

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

         scanf("%d%d",&cow[i].left,&cow[i].right);

     sort(cow,cow+n);

     int lright=,ans=,p=-;

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

     {

         if (cow[i].left>lright+)

         {

             if (p==-) break;

             /*如果当前左边界已经大于之前的最大右边界，且没有中间区间能衔接，必定说明无解*/

             ans++;

             lright=p;

             p=-;

             /*否则将已经覆盖区域的右边界设为之前最大的右边界*/

         }

         if (cow[i].left<=lright+ && cow[i].right>=lright+)

         {

             p=max(p,cow[i].right);

             if (p>=t)

             {

                 ans++;

                 break;

                 /*如果当前已经覆盖完大区间，就退出*/

             }

         }

     }

     if (p>=t) cout<<ans<<endl;

         else cout<<-<<endl;

          return ;

 }

巴特西

【贪心】POJ2376-Cleaning Shifts

最新文章

热门文章