文章目录

• • • 题目分析
    • 题目来源

题目分析

来源：acwing

分析：求满足条件 M ≤ m × p M \leq m\times p M≤m×p的区间[m, M]最长是多少。此处有一性质：当最大值M变大的时候，最小值m也是变大的， 它不可能变小。根据这个性质便可以是使用双指针算法：先从小到大枚举最大值M，然后最小值m也是单调增加的。

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int n ,p;
int a[N];

int main(){
    cin >> n >> p;
    int cnt = -1;
    for(int i = 0; i< n; i++) cin>> a[i];
    sort(a,a+n);
    //i是最大值，j是最小值
    for(int i = 0, j = 0; i< n; i++){
       while((LL) a[j]* p <a[i]) j++;
       cnt = max( cnt, i - j +1);
    }
    cout<<cnt<<endl;
    
}

题目来源

PAT甲级1085 Perfect Sequence

https://www.acwing.com/problem/content/1573/