问题描述
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤105 ）是输入的正整数的个数，p（≤109）是给定的参数。第二行给出 N 个正整数，每个数不超过 109。输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
解决方法
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll arr[maxn];
//完美数列
int main(void)
{
int m = 0, p = 0;
scanf("%d %d", &m, &p);
for (int i = 0; i < m; i++)
{
scanf("%lld", arr + i);
}
sort(arr, arr + m);
int left = 0, right = 0;
int count = 0;
while (right != m)
{
if (arr[left] * p >= arr[right])
{
if (right - left + 1 > count)
{
count = right - left + 1;
}
right++;
}
else
{
left++;
}
}
printf("%d", count);
return 0;
}
基本策略
- 两个指针指向排序好的数组元素开头先以下标0为最小数寻求能找到最多数的最大的值的下标,记录下个数(cout)，之后继续寻找最大值最小值只需要在原有下标下进行增加即可。边界为最大值下标到末尾。因为之后提升最小值下标只会使得结果个数变小。没必要继续寻找。
结果展示
PatB1030.png
