AcWing 1571. 完美序列
原题链接
简单
作者:
偷月亮的喵
,
2024-11-08 16:46:33
,
所有人可见
,
阅读 1
/*
从序列中找到尽可能多的数字以构成一个完美的子序列 ——》这个子序列不是连续紧挨着的,所以可以进行排序
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, p;
long long a[N];//必须开long long
int main()
{
cin >> n >> p;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
long long ans = 0;
sort(a + 1, a + n + 1);
for (long long i = 1, j = 1; i <= n; i ++){//枚举右端点 i :最大值
while(a[i] > a[j] * p && j <= i){ // j :左端点,最小值
j++;
}
if(a[i] <= a[j] * p){
ans = max(ans, i - j + 1);
}
}
cout << ans << '\n';
return 0;
}