给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数N和p，其中N（<= 105）是输入的正整数的个数，p（<= 109）是给定的参数。第二行给出N个正整数，每个数不超过109。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例：
|
1 2 |
10 8 2 3 20 4 5 1 6 7 8 9 |
输出样例：
|
1 |
8 |
注意利用已经获得最大值对循环的过程进行优化即可，不然非常及其容易超时……
代码如下：
1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<stdio.h> #include<stdlib.h> //快排 int compare(const void *a,const void *b) { if(*(long *)a>*(long *)b) return 1; else if(*(long *)a<*(long *)b) return -1; else return 0; } int main() { long *num,*nums; int n,p; register int i,j,max=1; scanf("%d%d",&n,&p); num=(long *)malloc(n*sizeof(long)); nums=(long *)malloc(n*sizeof(long)); for(i=0;i<n;i++) { scanf("%ld",num+i); } qsort(num,n,sizeof(long),compare); for(i=0;i<n;i++) { nums[i]=num[i]*p; } for(i=0;i<n;i++) { if(i+max>n) break; for(j=i+max;j<n;j++) { if(nums[i]>=num[j]) { if(max<j-i+1) { max=j-i+1; } } else { break; } } } printf("%d\n",max); } |
2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
//堆排序 #include<stdio.h> #include<stdlib.h> void HeapAdjust(long array[],long i,long nLength) { long nChild; long nTemp; for(;2*i+1<nLength;i=nChild) { nChild=2*i+1; if(nChild<nLength-1&&array[nChild+1]>array[nChild]) ++nChild; if(array[i]<array[nChild]) { nTemp=array[i]; array[i]=array[nChild]; array[nChild]=nTemp; } else break; } } void HeapSort(long array[],long length) { long i; for(i=length/2-1;i>=0;--i) HeapAdjust(array,i,length); for(i=length-1;i>0;--i) { array[i]=array[0]^array[i]; array[0]=array[0]^array[i]; array[i]=array[0]^array[i]; HeapAdjust(array,0,i); } } int main() { long *num,*nums; int i,j,n,p,max=1; scanf("%d%d",&n,&p); num=(long *)malloc(n*sizeof(long)); nums=(long *)malloc(n*sizeof(long)); for(i=0;i<n;i++) { scanf("%ld",num+i); } HeapSort(num,n); for(i=0;i<n;i++) { nums[i]=num[i]*p; } for(i=0;i<n;i++) { if(i+max>n) break; for(j=i+max;j<n;j++) { if(nums[i]>=num[j]) { if(max<j-i+1) { max=j-i+1; } } else { break; } } } printf("%d\n",max); } |
3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<stdio.h> #include<stdlib.h> //快排，未优化，未AC int compare(const void *a,const void *b) { if(*(long *)a>*(long *)b) return 1; else if(*(long *)a<*(long *)b) return -1; else return 0; } int main() { long *num,*nums; int n,p; register int i,j,max=1; scanf("%d%d",&n,&p); num=(long *)malloc(n*sizeof(long)); nums=(long *)malloc(n*sizeof(long)); for(i=0;i<n;i++) { scanf("%ld",num+i); } qsort(num,n,sizeof(long),compare); for(i=0;i<n;i++) { nums[i]=num[i]*p; } for(i=0;i<n;i++) { if(n-i<max) break; for(j=n-1;j>=i;j--) { if(j-i<max) break; if(nums[i]>=num[j]) { if(max<j-i+1) { max=j-i+1; } break; } } } printf("%d\n",max); } |