84分求助,用了快速排序和二分还是tle
查看原帖
84分求助,用了快速排序和二分还是tle
1106587
Vegepuppy楼主2023/10/9 23:43

如题,试过把查找部分注释掉只保留排序,但是#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;
}
2023/10/9 23:43
加载中...