1085 Perfect Sequence

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 (≤105) is the number of integers in the sequence, and p (≤109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

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

题意

给定一个正整数序列和常量 p ，假设一个序列的最小值为 m 以及最大值为 M ，那么当 m*p>=M 时，该序列为完美序列，现在需要我们找到给定序列中完美子序列的元素最大个数。

思路

具体思路如下：

1.存入每个元素，并对这些元素进行升序排序。

2.使用双指针进行完美子序列的查找，其中 i 表示上界即最大值，j 表示下界即最小值，然后用 for 循环从小到大遍历 i ，每趟遍历中 j 再从 0 开始递增，直至不满足 a[j]*p<a[i] 。计算当前序列个数 i-j+1 ，如果大于当前存储的答案 res ，则更新 res 。

3.输出答案 res 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, p;
int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    //对数组进行排序
    sort(a, a + n);
    //双指针计算计算范围
    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        while ((long long)a[j] * p < a[i])  j++;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}