1030 完美数列

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

思路：

本题难度略大（一开始的时候想加快速度，定义了一个数，last=max/p，想从最小数循环到last就可以了，减少了几个循环，结果导致最后一个测试用例始终通过不了）

个人猜测最后一个案例可能类似是这样的（就是包括p有很多大数的情况）：

6 99999998
1 999999995 999999996 999999997 999999998 999999999

其实抛开这个测试点，整体的思路还是比较清晰的

首先读取所有的数存入数组中，然后使用sort进行排序：

    int N;
    double p;
    double n[100001];
    cin >> N >> p;
    for (int i = 0; i < N; i++)
    {
        scanf("%lf", &n[i]);
    }
    sort(n, n + N);

然后定义一个双循环，从小到大，计算每个数的完美序列的个数，将最大的存起来：

==注意内循环查找的时候可以从i+max开始，可以大大减少查找时间（不加的话有一个测试用例会运行超时）==

    int max = 1;//首先定max=1
    for (int i = 0; i < N; i++)//i从0开始循环
    {
        for (int j = i+max; j < N; j ++)//j从i+max开始判断可以减少很多不必要的判断，大大加快程序的运算速度
        {
            if (n[j] > p*n[i])//找到第一个比p*n[i]大的数的序号j
            {
                max = (j - i)>max ? (j - i) : max;//根据j与i的位置，计算这个数列的个数为j-i（因为j的前一个数字才满足完美数列要求，n[j]并不满足）
                break;
            }
            else if(n[j]==p*n[i]||j==N-1)//如果找到的是第一个等于p*n[i]，计算数列个数的时候要+1
            //当找到最后一个数字都没有满足>=的情况的时候，证明i后面所有的数字都可以组成完美序列，也要停止
            {
                max = (j - i + 1) > max ? (j - i + 1) : max;
                break;
            }
        }
    }

最后输出max即可。

代码：

完美数列

//1030 完美数列
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int N;
    double p;
    double n[100001];
    cin >> N >> p;
    for (int i = 0; i < N; i++)
    {
        scanf("%lf", &n[i]);
    }
    sort(n, n + N);
  int max = 1;//首先定max=1
  for (int i = 0; i < N; i++)//i从0开始循环
  {
    for (int j = i+max; j < N; j ++)//j从i+max开始判断可以减少很多不必要的判断，大大加快程序的运算速度
    {
      if (n[j] > p*n[i])//找到第一个比p*n[i]大的数的序号j
      {
        max = (j - i)>max ? (j - i) : max;//根据j与i的位置，计算这个数列的个数为j-i（因为j的前一个数字才满足完美数列要求，n[j]并不满足）
        break;
      }
      else if(n[j]==p*n[i]||j==N-1)//如果找到的是第一个等于p*n[i]，计算数列个数的时候要+1
      //当找到最后一个数字都没有满足>=的情况的时候，证明i后面所有的数字都可以组成完美序列，也要停止
      {
        max = (j - i + 1) > max ? (j - i + 1) : max;
        break;
      }
    }
  }
    cout << max;
}