社区讨论
请大佬帮我
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 条回复,欢迎继续交流。
正在加载回复...