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;
}