PTA basic 1030 完美数列 (25 分) c语言实现(gcc)

 1 #include "stdio.h"
 2 #include "stdlib.h"
 3 //每次需要比较最大最小值,
 4 //给出的数据为乱序数组,需要有序化,需要对大量数据排序,因此算法效率是非常重要的,可以使用自带库函数qsort,原理是快排
 5 //在得出有序数组后,需要计算最大完美数列长度,从0位置开始分别统计从0到队尾的每个元素开始的完美数列长度,比较得出最大值
 6 
 7 typedef long ElementType;
 8 
 9 //快排 严蔚敏版
10 int partition(ElementType *a,int left,int right){
11     ElementType pivot=a[left];
12     while(left<right){
13         while(left<right&&a[right]>=pivot)--right;
14         a[left]=a[right];
15         while(left<right&&a[left]<=pivot)++left;
16         a[right]=a[left];
17     }
18     a[left]=pivot;
19     return left;
20 }
21 //手动实现快排
22 void quicksort(ElementType *a,int left,int right){
23     if(left<right){
24         int pivotpos=partition(a,left,right);
25         quicksort(a,left, pivotpos-1);
26         quicksort(a,pivotpos+1,right);;
27     }
28 }
29 
30 
31 //qsort的比较函数
32 int compare(const void *lp,const void *rp){
33     ElementType *l=(ElementType*)lp;
34     ElementType *r=(ElementType*)rp;
35     int result;
36     result=*l>*r?1:-1;
37     return result;
38 }
39 
40 int main(){
41     int n,i,j,currentlen=0,maxlen=0;
42     ElementType p;
43     scanf("%d %ld",&n,&p);
44     ElementType arrList[n];
45     for(i=0;i<n;i++)scanf("%ld",&arrList[i]);
46 //    quicksort(arrList,0,n-1);
47     qsort(arrList, n,sizeof(ElementType), compare);
48     for(i=0;i<n;i++){//从前到后找出每个位置开始的最长子列长度
49         for(j=i+currentlen;j<n;j++){//i+currentlen为已知最长完美数列的队尾下标+1
50             if(arrList[j]>arrList[i]*p){
51                 break;
52             }
53             currentlen=j-i+1;//元素i开始的完美队列当前长度
54             if(currentlen>maxlen)maxlen=currentlen;//如果当前子列的完美数列长度>已知的最大长度则更新
55         }
56     }
57     printf("%d",maxlen);
58     return 0;
59 }