1030 完美数列 （25 分)
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤105）是输入的正整数的个数，p（≤109）是给定的参数。第二行给出 N 个正整数，每个数不超过 109。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例：
10 8
2 3 20 4 5 1 6 7 8 9
输出样例：
8思路：
所有完美数列应该都是在数组的递增序列上的连续若干个数，所以应该先对数组排序，然后再寻找最大的完美数列。
codes
暴力版：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ; int main(){
long long n, p, num[maxn];
cin>>n>>p;
for(int i = ; i < n; i++) cin>>num[i];
sort(num, num + n);
int cnt = ;
for(int i = ; i < n; i++){
for(int j = i + cnt; j < n; j++){
if(num[j] > num[i] * p) break;
if(j-i+>cnt) cnt=j-i+;
}
}
cout<<cnt;
return ;
}
二分法：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
long long n,p,a[maxn];
int binarySearch(int i, long long x){
if(a[n-] <= x) return n;
int l = i + , r = n - , mid;
while(l < r){
mid = (l + r) / ;
if(a[mid] <= x) l = mid + ;
else r = mid;
}
return l;
}
int main(){
cin>>n>>p;
for(int i = ; i < n; i++){
cin>>a[i];
}
sort(a, a + n);
int ans = ;
for(int i = ; i < n; i++){
int j = binarySearch(i, a[i]*p);
if(j - i > ans) ans = j - i;
}
cout<<ans;
return ;
}
双指针：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
long long n,p,a[maxn]; int main(){
long long n,p,a[maxn];
cin>>n>>p;
for(int i=;i<n;i++) cin>>a[i];
sort(a,a+n);
int ans=,i=,j=;
while(i<n&&j<n){
while(j<n && a[j]<=a[i]*p){
if(j-i+>ans) ans = j-i+;
j++;
}
i++;
}
cout<<ans;
return ;
}