1030 完美数列 (25 分)

Question

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

int cmp(const void*,const void *);
int perfect(const int* num,int,int,int);

int cmp(const void* a,const void *b){
	int m=*(int *)a;
	int n=*(int *)b;
	
	return m>n;
}


int main(){
	
	int n,p,max=0;
	scanf("%d %d",&n,&p);
	int num[n];
	if (n==1){
        printf("1");
        return 0;
    }
	for (int i=0;i<n;i++){
		scanf("%d",&num[i]);
	}
	qsort(num,n,sizeof(int),cmp);//从小到大排序 
	int i=0,j=n-1;//i指向最小值，j指向最大值

	while (i<n-1){
		while (j>0){
			if (j>=(i+max)){
                if (num[j]<=(num[i]*p)){
                    int ans=j-i+1;
                    if (ans>max){
                        max=ans;
                        break;
                    }
                }
			}
			j--;
		}
		i++;
		j=n-1;
	}

	printf("%d",max);
	
	return 0;
}

各位大佬，我想问一下我的4和5测试点过不去，4是超时，5是答案错误

我的想法是先排序，然后i指向最小值，j指向最大值，i是外圈大循环，j是小循环

对于节约时间的问题，我已经使用(j>=i+max)，这样j就不会继续往小了走使得时间开销变大

请问各位大佬还能怎么改进时间复杂度呀？

Answer 1

C和C++完整教程：https://blog.csdn.net/it_xiangqiang/category_10581430.html
C和C++算法完整教程：https://blog.csdn.net/it_xiangqiang/category_10768339.html