LA 2322 Wooden Sticks

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <iostream>

 4  #include <algorithm>

 5  #include <map>

 6  using namespace std;

 7  struct stick

 8  {

 9      int a,b;

10      bool use;

11  };

12  bool cmp(stick lhs,stick rhs)

13  {

14      if(lhs.a!=rhs.a) return lhs.a<rhs.a;

15      else return lhs.b<rhs.b;

16  }

17  int main()

18  {

19      int cas;

20      cin>>cas;

21      while(cas--)

22      {

23          int n;

24          cin>>n;

25          stick sticks[5005];

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

27          {

28              int a,b;

29              cin>>a>>b;

30              sticks[i].a=a;

31              sticks[i].b=b;

32              sticks[i].use=false;

33          }

34          sort(sticks,sticks+n,cmp);

35          int cur=0,ans=1;

36          sticks[0].use=true;

37          stick tmp=sticks[0];

38          while(1)

39          {

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

41              {

42                  if(sticks[i].use==false && sticks[i].a>=tmp.a && sticks[i].b>=tmp.b)

43                  {

44                      sticks[i].use=true;

45                      tmp=sticks[i];

46                  }

47              }

48              int j;

49              for(j=1;j<n;j++)

50              {

51                  if(sticks[j].use==false)

52                  {

53                      ans+=1;

54                      sticks[j].use=true;

55                      cur=j;

56                      tmp=sticks[j];

57                      break;

58                  }

59              }

60              if(j==n) break;

61          }

62          cout<<ans<<endl;

63      }

64      return 0;

65  }