算法训练

算法训练"/>

算法训练

7-2 Perfect Sequence (50分)
7-2完全序列(50分）

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
翻译：给出了一个正整数序列和另一个正整数p，该序列称为“完全序列”，如果M≤m*p，其中M和m分别是序列中的最大数和最小数。

现在给定一个序列和一个参数p，你应该从序列中找到尽可能多的数字，从而形成一个完全的子序列。

Input Specification:输入格式：

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10⁵ ) is the number of integers in the sequence, and p (≤10⁹) is the parameter. In the second line there are N positive integers, each is no greater than 10⁹.
翻译：每个输入文件包含一个测试用例。对于每一种情况，第一行包含两个正整数N和p，其中N(≤10⁵)是序列中整数的数目，P(<10⁹)是参数。在第二行中有N个正整数，每个整数都不大于10⁹.

Output Specification:输出格式：

​​For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
翻译：对于每个测试样例，在一行中打印可以选择以形成完全子序列的最大整数数。

Sample Input:输入样例：

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:输出样例：

8

C++代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>typedef long long ll;
using namespace std;
const int N=1e5+10;
const int maxn=1e5+10;
int main()
{int n,mx=0;ll p;scanf("%d%lld",&n,&p);vector<ll>v(n);for(int i=0;i<n;i++)scanf("%lld",&v[i]);sort(v.begin(),v.end());for(int i=0;i<n;i++){int ls=upper_bound(v.begin(),v.end(),v[i]*p)-v.begin();if((ls-i)>mx)mx=ls-i;}cout<<mx<<endl;return 0;
}

小提示：

比赛前可以先将系统头文件都写到电脑记事本里，拿到题目后直接粘贴，对代码运行时间没有影响，
因为不调用相应头文件里的函数，就不会运行相应的头文件。