1030 完美数列 （20）(测试点4，5)

给定一个正整数数列，和正整数?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

?这道题目我想到的思路其实很简单：

它不是让我们求M<=m*p的最大长度嘛，所以，我们可以先将我们的输入数组进行排序然后，从小到大依次遍历，每个乘以p然后找出第一个大于m*p的索引值减去当前索引，这就是一个完美队列的长度，我们依次遍历，找出最长的长度为止。

但是测试点4和测试点5难住了我，经过我的多次测试我发现了关于这两个测试点的解决方法。下面我会提及我的方法的。

//完整代码
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, p;
    int arr[100000]={0};
    int max=0;
    cin >> N >> p;

    for (int i = 0; i < N; i++) {      //输入
        cin >> arr[i];
    }
    
    sort(arr, arr + N);                // 排序，升序
    int j=0;
    for(int i=0;i<N;i++){
        long m=arr[i];      //记录m*p值   一定要写long不然测试点5错误
        while (m*p>=arr[j]&&j<N) {
            j++;
        }
        int cha=j-i;
        if(cha>max){    //更新最大长度
            max=cha;
        }
    }
    cout <<max;
    

    return 0;
}

?步骤：

输入——排序——遍历（从小到大，索引值相减得到长度）——更新最大长度——输出

测试点4：测试点4是一个庞大输入的测试点，我们很容易会运行超时，就比如在遍历的时候，一个变量定义的位置搞不好都会导致超时：

//正确的遍历
int j=0;
for(int i=0;i<N;i++){
    long m=arr[i];      //记录m*p值   一定要写long不然测试点5错误
    while (m*p>=arr[j]&&j<N) {
         j++;
    }
    int cha=j-i;
    if(cha>max){    //更新最大长度
        max=cha;
    }
 }

//错误的遍历
for(int i=0;i<N;i++){
    long m=arr[i];      //记录m*p值   一定要写long不然测试点5错误

    int j=i;                 //定义放在里面

    while (m*p>=arr[j]&&j<N) {
        j++;
    }
    int cha=j-i;
    if(cha>max){    //更新最大长度
        max=cha;
    }
}

就是这一个很小的点，我把int j=0的定义放在外面就不会导致报错，而我放在里面（当时我还觉得我将int j=i这样也会减少循环次数呢）就会导致运行超时。

所以我们还是需要注意变量定义的位置的。

?而测试点5也是把我搞糊涂了，解决方法是在遍历的时候，我们需要将输入值改成long型才行。注意long m=arr[i];不能在这一步将他写成long mp=arr[i]*p理由就是其中?arr[i]?和?p?都是整型变量。在这种情况下，乘法运算将按照整型运算进行，并且结果的类型也是整型。如果乘法操作的结果超出了整型的范围，就会导致溢出，得到错误的结果。

?