uva 10020 Minimal coverage

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=961
欲張り、ソート、左端に欲張り、最大右端を探します.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #define maxn 6000000

 5 using namespace std;

 6 

 7 int t,m;

 8 int t1;

 9 int ll[maxn],rr[maxn];

10 struct node

11 {

12     int l,r;

13     int id;

14     bool operator <(const node &a)const

15     {

16         return (l<a.l)||(l==a.l&&r>a.r);

17     }

18 } p[maxn],ans[maxn];

19 

20 int main()

21 {

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

23     while(t--)

24     {

25         t1=0;

26         scanf("%d",&m);

27         int cnt=0;

28         int l,r;

29         int num=0;

30         while(scanf("%d%d",&l,&r)!=EOF)

31         {

32             if(l==0&&r==0) break;

33             if(l>m||r<0) continue;

34             p[cnt].id=num;

35             p[cnt].l=l;

36             p[cnt++].r=r;

37         }

38         sort(p,p+cnt);

39         bool flag1=false;

40         int ll=0,rr=0;

41         while(1)

42         {

43             if(ll>=m)

44             {

45                 break;

46             }

47             flag1=false;

48             rr=0;

49             int pos;

50             for(int i=0; i<cnt; i++)

51             {

52                 if(p[i].l<=ll&&p[i].r>rr)

53                 {

54                     pos=i;

55                     rr=p[i].r;

56                     flag1=true;

57                 }

58             }

59             if(flag1)

60             {

61                t1++;

62                ans[t1]=p[pos];

63                ll=rr;

64             }

65             else break;

66         }

67         if(flag1)

68         {

69             printf("%d
",t1);

70             for(int i=1; i<=t1; i++)

71             {

72                 printf("%d %d
",ans[i].l,ans[i].r);

73             }

74         }

75         else printf("0
");

76     }

77     return 0;

78 }

View Code