pat甲级1085

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 (≤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:

第一种方法：

用max记录当前的最长序列长度，因为是要找出最大长度，因此对于每个i，只需要让j从i + max开始。

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 vector<int> v;

 int main()

 {

     int N, i, j;

     long p;

     cin >> N >> p;

     v.resize(N);

     for (i = ; i < N; i++) cin >> v[i];

     sort(v.begin(), v.end());

     int t, max = ;

     for (i = ; i < N; i++)

     {

         for (j = i + max; j < N && v[j] <= v[i] * p; j++);

         if (j - i > max) max = j - i;

     }

     cout << max;

     return ;

 }

关于lower_bound()和upper_bound()的使用：

在从小到大的排序好的数组中：

（lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

来源：CSDN
原文：https://blog.csdn.net/qq_40160605/article/details/80150252 ）

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> v;

int main()

{

    int N, i, j;

    long p;

    cin >> N >> p;

    v.resize(N);

    for (i = ; i < N; i++) cin >> v[i];

    sort(v.begin(), v.end());

    int t, max = ;

    for (i = ; i < N; i++)

    {

        t = upper_bound(v.begin() + i, v.end(), v[i] * p) - (v.begin() + i);

        if (t > max) max = t;

    }

    cout << max;

    return ;

}

参考：

https://www.liuchuo.net/archives/1908

巴特西