【PAT甲级】1085 Perfect Sequence (25 分)


题目要求

给定一个正整数序列和一个正整数 p。

如果 M ≤ m × p M≤m×p Mm×p 成立,则该序列被称为完美序列,其中 M 和 m 分别是序列中的最大和最小数。

现在给定一个序列和一个参数 p,你应该从序列中找到尽可能多的数字以构成一个完美的子序列。


思路

  • 先对数组进行排序
  • 该题符合双指针算法,因为当找到一个完美序列的时候,若i指向最大值,j指向最小值,那么此时下一个完美序列的 i’ 一定在i的右侧,j’ 一定在j的右侧(可以由 M ≤ m × p M≤m×p Mm×p 推出)
  • 暴力做法复杂度 O ( n 2 ) O(n^2) O(n2),双指针算法复杂度为 O ( n ) O(n) O(n)

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
long long int a[N];
int main()
{
    long long int n,p;
    cin>>n>>p;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for(int i=0,j=0;i<n;i++)
    {
        while(j<n&&a[i]>a[j]*p) j++;
        res=max(res,i-j+1);
    }
    cout<<res;
    return 0;
}