PAT (Basic Level) Practice （中文）1030 完美数列 (25 分)
1030 完美数列 (25 分)
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤105）是输入的正整数的个数，p（≤109）是给定的参数。第二行给出 N 个正整数，每个数不超过 109。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例：
10 8
2 3 20 4 5 1 6 7 8 9输出样例：
8首先，先排序，线性遍历一遍，扫到a[i]时，upperbound找出第一个比 k*a[i]大的数a[p]，那么对于a[i]这个元素而言，p-1就是满足完美数列且元素数最多的最大值的那个下标，不断与最大值比较即可~
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 300005
#define lb(x) (x&(-x))
const double eps = 1e-6;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
set<ll>t;
ll n,k,a[maxn];
int main()
{
cin>>n>>k;
for(rg i=1;i<=n;i++)
{
a[i]=read();
}
sort(a+1,a+1+n);
ll maxx=-inf;
for(rg i=1;i<=n;i++)
{
//cout<<upper_bound(a+1,a+1+n,a[i]*k)-a-1<<endl;
maxx=max(maxx,upper_bound(a+1,a+1+n,a[i]*k)-a-i);
}
cout<<maxx<<endl;
return 0;
}举报
腾讯云开发者
