MDOLLS - Nested Dolls

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
#include <cstdlib>
#include <algorithm>
//#include <conio.h>

using namespace std;

struct doll{
    int rong,cao;
};

doll A[22222];
int f[22222],test,n,so;
/*
int cmp(const void *a,const void *b)
{
   doll  ta= *( doll*)a;
   doll  tb= *( doll*)b;
  

  if (ta.rong == tb.rong)
  return tb.cao  - ta.cao;
    return ta.rong - tb.rong;
  //return tb->cao  - ta->cao;

}
*/
int cmp(const void *a,const void *b)
{
    doll X = *( doll*)a;
    doll Y = *( doll*)b;
    if(X.rong==Y.rong) return Y.cao-X.cao;
    return X.rong - Y.rong;
}

int main()
{
   // freopen("MDOLLS.in","r",stdin);
    scanf("%d",&test);
    while(test--){
        scanf("%d",&n);
        for(int i = 0;i<n;i++) scanf("%d %d",&A[i].rong,&A[i].cao);
       // memset(f,0,sizeof(f));
        qsort(A,n,sizeof(struct doll),cmp);
        so = 0;
        int be,lon;
        for(int i = 0;i<n;i++){
             be = 0;
             lon = so;
             while(lon>be)
             {
                  int tb = (lon+be)/2;
                  if(f[tb]>=A[i].cao)
                      be = tb+1;
                  else lon = tb;
             }
             f[be] = A[i].cao;
             so += (be==so);
        }
        printf("%d\n",so);
    }
   // getch();
}

Download