PAT甲级1085 Perfect Sequence ：[C++题解]双指针

文章目录

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

题目分析

来源：acwing

分析：求满足条件$M\le m\times 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/

总结

以上是生活随笔为你收集整理的PAT甲级1085 Perfect Sequence ：[C++题解]双指针的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。