如题,试过把查找部分注释掉只保留排序,但是#2#3还是tle。
#include<stdio.h>
unsigned a[200000] ={0};
int ans = 0;
void Quicksort(unsigned a[],int low,int high)
{
int i = low, j = high, key = a[i];
while(i<j)
{
while(i<j&&a[j]>=key)
j--;
a[i] = a[j];
while(i<j&&a[i]<=key)
i++;
a[j] = a[i];
}
a[i] = key;
if(i+1<high)
Quicksort(a,i+1,high);
if(i-1>low)
Quicksort(a,low,i-1);
return ;
}
int Find(x,end)
{
int start = 0, ret = 0, mid = 0, num = -1;
do{
mid = (start+end)/2;
if(a[mid] == x)
{
ret = 1;
num = mid;
break;
}
else if(a[mid]<x)
start = mid+1;
else
end = mid-1;
}while(start<=end);
int p = num;
if(num != -1)
{
while(a[p-1] == a[p])
{
p--;
ret++;
}
while(a[num+1] == a[num])
{
num++;
ret++;
}
}
return ret;
}
main()
{
int n = 0, c = 0,tem;
scanf("%d%d",&n,&c);
int i = 0, j = 0;
for(i = 0; i<n; i++)
{
scanf("%d",a+i);
}
Quicksort(a,0,n-1);
for(i = n-1; i>0; i--)
{
if(a[i] != -1)
{
tem = Find(a[i]-c,i-1);
ans += tem;
if(tem)
a[i] = -1;
}
}
printf("%d",ans);
return 0;
}