# A1085

1085 Perfect Sequence (25 分)

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.

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 ​5 ​​ ) is the number of integers in the sequence, and p (≤10 ​9 ​​ ) is the parameter. In the second line there are N positive integers, each is no greater than 10 ​9 ​​ .

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

## 法1

``````#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n;
long long m;    //由于m*sque[i]可能会超过int，所以将m设为long long型
int maxLength = 0;  //完美序列的最大长度

int main()
{
scanf("%d%lld", &n, &m);
vector<int> sque(n);
for (int i = 0; i < n; i++)
{
scanf("%d", &sque[i]);
}
sort(sque.begin(), sque.end());
for (int i = 0; i < n; i++) //从序列小的开始，找到以sque[i]为最小值的最长完美序列
{
//因为sque[i]的最长完美序列为maxLength，其尾元素就是sque[i+maxLength]
//那么sque[i+1]的最长完美序列的尾元素必定大于等于sque[i+maxLength],所以直接在i+maxLength处开始找即可
for (int j = i + maxLength; j < n;j++)
{
if(sque[i]*m>=sque[j])
{
int tempLength = j - i + 1;
if(tempLength>maxLength)
maxLength = tempLength;
}
else    //找到最大尾元素了即终止本次查找
break;  //此句不加测试点4超时
}
}
printf("%d", maxLength);
}
``````

## 法2

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, maxLength = 0;
long long m;

int main()
{
scanf("%d%lld", &n, &m);
vector<int> sque(n);
for (int i = 0; i < n;i++)
{
scanf("%d", &sque[i]);
}
sort(sque.begin(), sque.end());
for (int i = 0; i < n;i++)
{
int tempLength = upper_bound(sque.begin(), sque.end(), sque[i] * m) - sque.begin() - i;
if(tempLength>maxLength)
maxLength = tempLength;
}
printf("%d", maxLength);
return 0;
}
``````