请大佬帮我
查看原帖
请大佬帮我
1183214
Liuliubangbang楼主2024/10/8 18:02

写了个(nlogn),但是不知道为何会错误。 样例过了。

#include<stdio.h>
#include<stdlib.h>

void Init_arry(int *a, int n);
void Sort_arry(int *a, int n);
void Msort(int *a, int *t, int Num, int Length);
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd);
int Binary_count(int *a, int i, int n, int k);
int count_num(int *a, int n, int k);

int main()
{
	int n, k;
	int *a;
	int count;
	scanf("%d %d", &n, &k);
	a = (int*)malloc(sizeof(int) * n);
	Init_arry(a, n);
	count = count_num(a, n, k);
	printf("%d\n", count);
	free(a);
	return 0;
}
void Init_arry(int *a, int n)
{
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	Sort_arry(a, n);
	return ;
}
void Sort_arry(int *a, int n)
{
	int *t;
	int Length = 1;
	t = (int *)malloc(sizeof(int) * n);
	if(t != NULL){
		while(Length < n){
			Msort(a, t, n, Length);
			Length *= 2;
			Msort(t, a, n, Length);
			Length *= 2;
		}
		free(t);
	}
}
void Msort(int *a, int *t, int Num, int Length)
{
	int i, j;
	for(i = 0; i <= (Num - 2 * Length); i += 2 * Length){
		Merge(a, t, i, i + Length, (i + 2 * Length) - 1);
	}
	if(i + Length < Num){
		Merge(a, t, i, i + Length, Num - 1);
	}else{
		for(j = i; j < Num; j++){
			t[j] = a[j];
		}
	}
}
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd)
{
	int LeftEnd, Nums;
	int Temp;
	LeftEnd = RightStart - 1;
	Temp = LeftStart;
	Nums = RightEnd - LeftStart + 1;
	while((LeftStart <= LeftEnd) && (RightStart <= RightEnd)){
		if(a[LeftStart] <= a[RightStart]){
			t[Temp++] = a[LeftStart++];
		}else{
			t[Temp++] = a[RightStart++];
		}
	}
	while(LeftStart <= LeftEnd){
		t[Temp++] = a[LeftStart++];
	}
	while(RightStart <= RightEnd){
		t[Temp++] = a[RightStart++];
	}
}
int Binary_count(int *a, int i, int n, int k)
{
	int Left = i;
	int Right = n - 1;
	int mid;
	while(Left <= Right){
		mid = (Left + Right) / 2;
		if(a[mid] * a[i] <= k){
			Left = mid + 1;
		}
		else{
			Right = mid - 1;
		}
	}
	return mid - i;
}
int count_num(int *a, int n, int k)
{
	int cnt = 0;
	for(int i = 0; i < n; i++){
		cnt += Binary_count(a, i, n, k);
	}
	return cnt;
}
2024/10/8 18:02
加载中...