1.找出满足M <= m * p要求的最长子序列，其中M为子序列里面的最大值，m为最小值。
2.先对输入的数据进行排序。
3.开始遍历所有情况，其中i从0开始遍历，求得j，使得num[j]<=num[i]*p，用二分法去查找j，把满足情况的都个数记录并取最大值。
4.不用二分法的话，第5个测试点会超时。
5.使用long long存储数据，后续的比较中，因为p<=10^9,num的最大值可以是10^9,超过32位int型，需要使用long long，才能通过最后一个测试点。
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 (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.
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
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
7 10
1 10 11 12 13 14 15
10 8
2 3 20 4 5 1 6 7 8 9
2 1
2 3
10 0
2 3 20 4 5 1 6 7 8 9
*/
int main(void)
{
int n, p;
cin >> n >> p;
vector<long long> num(n);
for (int i = 0; i < n; i++)
{
scanf("%d", &num[i]);
}
int maxSize = 0;
sort(num.begin(), num.end());
for (int i = 0; i < n; i++)
{//从i=0开始遍历
long long tmp = num[i] * p;
int l = i;
int r = n – 1;
while (l <= r)
{//采用二分法查找
int mid = (l + r) / 2;
if (num[mid] <= tmp)
{
l = mid + 1;
maxSize = max(maxSize, mid + 1 – i);//满足情况的数值都进行比较
}
else
{
r = mid – 1;
}
}
}
cout << maxSize << endl;
return 0;
}
[/c]