社区讨论

请大佬帮我

P8834 [传智杯 #3 决赛] 序列参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m209xueg
此快照首次捕获于
2024/10/08 18:04
去年
此快照最后确认于
2025/11/04 17:38
4 个月前
查看原帖
写了个(nlogn),但是不知道为何会错误。 样例过了。
C
#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;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...