FIRS - Hàng cây
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 n,A[100002],a[100002],Free[100002],u=1,v,dem=0;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
scanf("%ld",&A[i]);
a[i]=i; Free[i]=0;
}
A[n+1]=0;
Quicksort(A,a,1,n);
while(u!=n&&u!=n+1)
{
if(A[u]!=A[u+1])
u++;
else
{
v=u+1;
while(A[v]==A[v+1])
v++;
Quicksort(a,Free,u,v);
u=v+1;
}
}
//printf("%ld %ld %ld ",n,a[1],Free[a[1]]);
for(long i=1;i<=n;i++)
if(Free[a[i]]==0)
{
Free[a[i]]=1;
Free[a[i]-1]=1;
Free[a[i]+1]=1;
dem++;
}
printf("%ld",dem);
//getch();
}