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();
}