ural 1303 Minimal Coverage(贪心)

链接：

http://acm.timus.ru/problem.aspx?space=1&num=1303

按照贪心的思想，每次找到覆盖要求区间左端点时，右端点最大的线段，然后把要求覆盖的区间改为这个右端点到M这个区间。依次类推下去，这样的话就只需要扫一遍就可以找去来。

要做的预备工作就是将线段按照左端点的升序排序就可以了。

它的时间复杂度就是O(n)

代码一直WA，望大神指教

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<map>

 #include<vector>

 #include<set>

 #include<stack>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<stdlib.h>

 using namespace std;

 #define MAX(a,b) (a > b ? a : b)

 #define MIN(a,b) (a < b ? a : b)

 #define MAXN  200005

 #define INF 1000000007

 #define mem(a) memset(a,0,sizeof(a))

 #define judge(i) (ma[i].l<=L && ma[i].r>=L && ma[i].l != ma[i].r)//判断是否覆盖了点L

 struct node{int l,r;}ma[MAXN];

 int ans[MAXN];

 int M,N,T;

 int L;

 int cmp(node a,node b)

 {

     if(a.l != b.l)return a.l<b.l;

     else return a.r<b.r;

 }

 int find_index(int s,int &i)//找到覆盖了点L而且右端点最大的点，并返回；

                             //同时将后面要覆盖的点设置为它的右端点

 {

     i = s;

     int e = s,endd = ma[i].r;

     while(i < N && judge(i) )

     {

         if(ma[i].r > endd)

         {

             endd = ma[i].r;

             e = i;

         }

         i++;

     }

     L = endd;//endd就是满足覆盖条件下的最大的右端点

             //并将其设置为下次比较的左端点

     return e;//返回此次的线段的下标

 }

 int main()

 {

     while(~scanf("%d",&M))

     {

         N=;

         int i;

         mem(ans);

         while(scanf("%d%d",&ma[N].l, &ma[N].r) && (ma[N].l || ma[N].r))

         {

             if(ma[N].r <= || ma[N].l>=M)ma[N].l = ma[N].r = INF;//吧在要求区间两端之外的线段去掉

                   //吧它的左右端点值赋值为INF，这样的话排序时自然就会到最后方，也就相当于不用考虑

             N++;

         }

         sort(ma,ma+N,cmp);

         L = ;//最初要被覆盖的点是0

         int num = ;

         for(i=;i<N;i++)

         {

             int t = i+;//将t设置为i+1，如果下面的judge成功，就会进入函数的while中，那么i会++，如果不成功，t=i+1

             if(judge(i))   ans[num++] = find_index(i,t);

             i = t-;//由于t相当于多+了1，所以-1

             if(L >= M)break;//一旦找到，就退出循环

         }

         if(L < M)printf("No solution\n");

         else

         {

             printf("%d\n",num);

             for(i=;i<num;i++)

             {

                 printf("%d %d\n",ma[ans[i]].l,ma[ans[i]].r);

             }

         }

     }

     return ;

 }