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代码:
//#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; }