PAT甲级-1085 Perfect Sequence

题目

 

题目大意

在一组数中找到一个完美数列，满足M <= mp，M是该数列的最大值，m是最小值，p是题目给定的一个常数。

思路

模拟或者二分法。二分法可用upper_bound()函数实现。

知识点

upper_bound() 和 lower_bound() 函数在<algorithm>头文件中，一般有四种方式。

upper_bound(v.begin(), v.end(), value) 用于从小到大排列的数组，函数返回第一个>value的数的迭代器（地址）。

lower_bound(v.begin(), v.end(), value) 用于从小到大排列的数组，函数返回第一个>=value的数的迭代器（地址）。

upper_bound(v.begin(), v.end(), value, greater<int>()) 用于从大到小排列的数组，函数返回第一个<value的数的迭代器（地址）。

lower_bound(v.begin(), v.end(), value, greater<int>()) 用于从大到小排列的数组，函数返回第一个<=value的数的迭代器（地址）。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main(){long long n, p;cin >> n >> p;vector<long long> v(n);for (long long i = 0; i < n; i++){cin >> v[i];}sort(v.begin(), v.end());long long res = 0; // 最大距离for (int i = 0; i < n; i++){// 找到满足 v[j] <= v[i] * p 的最大 jauto it = upper_bound(v.begin(), v.end(), v[i] * p);res = max(res, (long long)(it - v.begin() - i));  // 强制转换为long long}cout << res << endl;return 0;
}
/*  当使用 upper_bound 返回第一个大于 v[i] * p 的位置后，前面的所有元素都会自动满足 <= v[i] * p，因为数组是升序排序的。这意味着从 v[i] 开始直到 upper_bound 返回的位置的所有元素，都是满足条件的。
*/