1085 Perfect Sequence

题目

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

分析

本题要求的是一个序列，因此就是从这N个数中选择若干个就可以了（不是子串）。看题目条件，要求选出的数中的最大值不超过最小值的p倍。为了方便处理，我们可以先将序列进行排序，这样问题就转化成了求一个子串的问题了。对于这种的问题，最常见的做法就是双指针。设置两个指针作为区间的左右端点，然后根据条件进行滑动，最终取最大值即可。但是本题还有一种做法，对于有序序列而言，求一个特定条件的数字，用二分查找无疑是最快的方法。因此，本题一共有两（三）种解法，下面直接看代码。

代码

1. 二分

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include <climits>
   
   using namespace std;
   
   vector<int> a;
   int N, p;
   
   bool binsearh(int pos, long long bound){
       if(a[N-1] <= bound){
           return N;
       }
       int l = pos+1, r = N-1, mid;
       while(l<r){
           mid = (l+r)/2;
           if(a[mid]<=bound){
               l = mid+1;
           } else{
               r = mid;
           }
       }
       return l;
   }
   int main(){
       scanf("%d %d", &N, &p);
       a.resize(N);
       int M=0, m=INT_MAX;
       for (int i = 0; i < N; ++i) {
           scanf("%d", &a[i]);
       }
   //    int i=0, j=0;
       int ans = 0;
       sort(a.begin(), a.end());
       for (int i = 0; i < N; ++i) {
           int x = binsearch(i, (long long)a[i]*p);
           ans = max(ans, x-i);
       }
       printf("%d", ans);
       return 0;
   }

2. std::upper_bound

   这里先补充一下，std库中有两个三个二分搜索的实现，其中upper_bound和lower_bound用法比较相似：

   // 在a.begin()到a.end()范围内，搜索第一个大于bound的元素，返回其迭代器
   upper_bound(a.begin(), a.end(), bound);
   // 在a.begin()到a.end()范围内，搜索第一个大于等于bound的元素，返回其迭代器
   lower_bound(a.begin(), a.end(), bound);

   目前来看，这两个函数的唯一区别就是是否可以等于。下面看代码：

   //
   // Created by masterCai on 2020/5/23.
   //
   
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main(){
       int n, p;
       scanf("%d %d", &n, &p);
       vector<int> a(n);
       for (int i = 0; i < n; ++i) {
           scanf("%d", &a[i]);
       }
       sort(a.begin(), a.end());
       int ans = 0;
       for (int i = 0; i < n; ++i) {
           int x = upper_bound(a.begin(), a.end(), (long long)a[i]*p)-a.begin();
           ans = max(ans, x-i);
       }
       printf("%d", ans);
       return 0;
   }

3. 双指针

   //
   // Created by masterCai on 2020/5/23.
   //
   
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main() {
       int n, p;
       scanf("%d %d", &n, &p);
       vector<int> a(n);
       for (int i = 0; i < n; ++i) {
           scanf("%d", &a[i]);
       }
       sort(a.begin(), a.end());
       int i=0, j=0;
       int ans = 0;
       while (i<=j && j<n){
           if((long long)a[i]*p>=a[j]){
               j+= 1;
           } else{
               i += 1;
           }
           ans = max(ans, j-i);
       }
       printf("%d", ans);
       return 0;
   }