1030 完美数列 (25 分)（滑动窗口）

目录

• • 一.题目
  • 二.分析
  • 三.代码
  • 四.结果

一.题目

二.分析

∙ \bullet ∙ 我们为了寻找满足题意的数字，那么首先第一步就得先将数列进行排序，然后依此从前往后查找。

∙ \bullet ∙ 在这里我使用了

滑动窗口

，避免重复进行计算。在循环时只要遵循两个式子就可以搜得最后结果。当满足题目条件时就将 r i g h t right right 加一，并且计算更新此时的数列长度，当不满足时就将 l e f t left left 加一。

∙ \bullet ∙ 注意题目中给出的 p p p 极大，所以需要使用 l o n g   l o n g long \ long long long 进行定义。

三.代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int N=0;
    long long p=0;
    cin>>N>>p;
    vector<int>num(N,0);  //记录数列
    for(int i=0;i<N;i++) cin>>num[i];
    sort(num.begin(),num.end());  //排序数列
    int res=0;
    int left=0,right=0; //左右端口
    while(left<=right && right<N)
    {
        if(num[right]>num[left]*p) left++;
        else
        {
            right++;
            res=max(res,right-left);
        }
    }
    cout<<res;
    return 0;
}
           

四.结果