PAT A1085 Perfect Sequence (25 分)/B 1030 完美数列 (25 分)
PAT A1085 Perfect Sequence (25 分)/B 1030 完美数列 (25 分)
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 (≤10^ 5 ) is the number of integers in the sequence, and p (≤10^ 9 ) is the parameter. In the second line there are N positive integers, each is no greater than 10^ 9 .
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:
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output:
8
B 1030 完美数列 (25 分) 中文题目：
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤10^ 5 ）是输入的正整数的个数，p（≤10^ 9 ）是给定的参数。第二行给出 N 个正整数，每个数不超过 10^ 9 。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例：
10 8
2 3 20 4 5 1 6 7 8 9
输出样例：
8
以下是AC的代码：
#include<cstdio>//二分法 #include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn = 100100;long long num[maxn]={0};long long n,p;bool cmpll(long long a,long long b){return a<b;}int findps(long long i,long long j){//从当前位置开始，找最大数字； long long left=i,right=j,sta=num[i]*p;while(left<right){long long mid=(left right)/2;if(sta <num[mid]) right=mid-1;else left=mid 1;}return left-i;}int main(void){scanf("%lld%lld",&n,&p);for(long long i=0;i<n;i ){scanf("%lld",&num[i]);}sort(num,num n,cmpll);int maxnum=0;//最大数字； for(long long i=0;i<n;i ){int number=findps(i,n);if(number>maxnum) maxnum=number; }printf("%d",maxnum);return 0;}思路：
这道题如果直接暴力枚举会运行超时，时间复杂度是O(n^ 2),但是用 二分法和 two pointers 的方法都可以解决。以下是用 two pointers 方法的代码：
//two pointers#include<cstdio>#include<algorithm>using namespace std;const int maxn = 100100;long long num[maxn]={0};bool cmpn(long long a,long long b){return a<b;}int main(void){long long n,p;scanf("%lld%lld",&n,&p);for(long long i=0;i<n;i ){scanf("%lld",&num[i]);}sort(num,num n,cmpn);long long i=0,j=0;long long count=0,maxnum=0;while(i<n&&j<n){count=0;//重置count; while(j<n&&p*num[i]>=num[j]){j ;}//j右移;count=j-i; if(count>maxnum) maxnum=count;while(i<=j&&p*num[i]<num[j]) i ;//i右移； }printf("%lld",maxnum);return 0;}