1030 完美数列 (25 分)

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤m*p，则称这个数列是完美数列。
现在给定参数 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

方法一（本人自己写的没用利用二分查找，而是用的循环里面套循环，左右两侧向中间逼近寻找最大值的方法。第四个测试点运行超时。）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
    long long n,p,M,m,a[100100]={0},maxlen=1;
    scanf("%lld %lld",&n,&p);
    for(int i=0;i<n;i++){//读取数列进入数组 
        scanf("%lld",&a[i]); 
    }
    sort(a,a+n);//增序排列 
    for(long long i=0;i<n;i++){//外层从0到n-1 
        for(long long j=n-1;j>=i;j--){//内层从n-1到i 
            long long M=a[j];//最大值 
            long long m=a[i];//最小值 
            if( M<=(m*p) )
            maxlen=max(maxlen,j-i+1);
        }
    }
    printf("%lld\n",maxlen);
    return 0;
}

方法二（参考算法笔记中的外层用循环遍历，循环里面套二分查找法）

方法三（参考算法笔记中two pointer法，将时间复杂度从O(n²)变成O(n)，事实上就是将方法一的双重循环改进了。利用数组递增的特性加以修改，使得“外面一层用循环遍历一遍，循环里面用循环再遍历一遍”变成了“左边的下标往右移动一次，右边的下标往左移动一次）

//刚开始的思路，L表示坐最小值的下标，R表示最大值的下标
//发现这样循环数组写不出，会卡住
while(L<=R){
        if((M/m)<=p) break;//如果满足题意停止循环
        else if((M/m)>p) R-=1;//如果M/m>p那么不管L是多少M/m>p都成立，此时令R左移一位
        else if(??) L+=1;//但是这里L怎么处理呢？换个思路把
        m=a[L];M=a[R];
    }

//如果L和R都从最左边开始移动呢
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    int p,m,M,a[100010],L=0,R=0,maxlen,extreme=1;
    //防止m*p过大超出数据类型范围导致程序错误，这里使用Long long型， 
    scanf("%d %d",&n,&p);
    for(int i=0;i<n;i++){
    //读取一行数列 
        scanf("%d",&a[i]); 
    }
    sort(a,a+n);
    //将数列按递增顺序排列 
    while(L<n&&R<n){
    //如果左标尺和右标尺都未超出数组下标范围 ，就一直循环 
        while(R<n&&a[R]<=(long long)p*a[L]){
        //如果一直满足条件，就一直让右边的标尺右移，不停地找L固定时地最大长度  
        //并且右边地标尺在每一次循环地时候不会归0，因为：符号大小的原因
            extreme=max(extreme,R-L+1);
            R++;
        }
        //左坐标的下标一直右移，不停地找L不同地时候地最大长度 
            L++;
    }
    printf("%d\n",extreme);
    //输出长度 
    return 0;
}