Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if $M\le m\times 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(\le 10^5)$ is the number of integers in the sequence, and $p(\le 10^9)$ is the parameter. In the second line there are N positive integers, each is no greater than $10^9$.

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

思路

• 双指针
• 注意minn*p 的大小是会超过int的,所以要使用long long比较
• 原题讲的是子序列而不是子串, 所选元素是可以不连续的,因此排序后, 一个连续序列的第一个元素就是最小值,最后一个元素就是最大值

AC code

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll=long long;
int main(){
    int n,p;
    scanf("%d %d",&n,&p);
    vector<int> v(n);
    for(int i=0;i<n;i++) scanf("%d",&v[i]);
    sort(v.begin(),v.end());
    int r=0,l=0;
    int maxn,minn,ans=0;
    
    //two pointers
    while(r<n){
        maxn = v[r];
        minn = v[l];
        r++;
        while((ll)maxn>(ll)minn*p and l<r){
            l++;
            minn = v[l];
        }
        ans = max(ans,r-l);
    }
    printf("%d",ans);
    return 0;
}