Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.
Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
Sample Input:
|
1 2 |
10 8 2 3 20 4 5 1 6 7 8 9 |
Sample Output:
|
1 |
8 |
PAT-Basic-1030. 完美数列的英文版。
代码如下：
|
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> 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); } |