MSTICK - Wooden Sticks
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
void Quicksort(long A[],long a[],long x,long y)
{
long t=A[(x+y)/2];
long i=x; long j=y;
while(i<=j)
{
while(A[i]<t) i++;
while(A[j]>t) j--;
if(i<=j)
{
long tg=A[i];
A[i]=A[j];
A[j]=tg;
long tga=a[i];
a[i]=a[j];
a[j]=tga;
i++;
j--;
}
}
if(j>x)
Quicksort(A,a,x,j);
if(i<y)
Quicksort(A,a,i,y);
}
main()
{
long T,n,A[5002],B[5002],Free[5002],dem=0,t,u,v,chay;
scanf("%ld",&T);
for(long i=0;i<T;i++)
{
scanf("%ld",&n);
dem=0;
for(long j=1;j<=n;j++)
{
scanf("%ld %ld",&A[j],&B[j]);
Free[j]=0;
}
A[n+1]=0;
Quicksort(A,B,1,n);
chay=1;
while(chay!=n&&chay!=n+1)
{
if(A[chay+1]>A[chay])
chay++;
else
{
u=chay;v=chay+1;
while(A[v+1]==A[v])
v++;
Quicksort(B,Free,u,v);
chay=v+1;
}
}
for(long j=1;j<=n;j++)
{
if(Free[j]==1)
continue;
t=j;
//printf("%ld",t);
for(long k=j+1;k<=n;k++)
{
if(B[k]>=B[t]&&Free[k]==0)
{
Free[k]=1;
t=k;
}
}
dem++;
}
printf("%ld\n",dem);
}
//getch();
}