PAT甲级 1085 Perfect Sequence 二分和双指针（Two Pointers）

本文主要是介绍PAT甲级 1085 Perfect Sequence 二分和双指针（Two Pointers），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分写法

#include <bits/stdc++.h>
using namespace std;
int find_upper_bound(const vector<long long>& nums, long long x)
{int beg = 0, end = nums.size(), mid = beg + (end - beg) / 2;while (beg < end) {mid = beg + (end - beg) / 2;if (nums[mid] <= x) {  // 第一个大于x的数一定在mid后面beg = mid + 1;}else {end = mid;  // 第一个大于x的数在mid之前（含mid）}}return end;  // 结束时有end=beg
}int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint N;long long p;cin >> N >> p;vector<long long> nums(N);for (int i = 0; i < N; ++i) {cin >> nums[i];}sort(nums.begin(), nums.end());int max_contain = -1;for (int i = 0; i < N; ++i) {long long x = nums[i] * p;int idx     = find_upper_bound(nums, x);max_contain = std::max(max_contain, idx - i);}cout << max_contain;
}

双指针（Two Pointers）

#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint n;long long p;cin >> n >> p;vector<long long> nums(n);for (auto& i : nums) cin >> i;sort(nums.begin(), nums.end());// i和j起点为0，i指示最小数字，j指示最大数字int i = 0, j = 0, ans = -1;while (j < n) {long long tmp = nums[i] * p;while (j < n && nums[j] <= tmp) ++j;ans = max(ans, j - i);++i;}cout << ans;
}

这篇关于PAT甲级 1085 Perfect Sequence 二分和双指针（Two Pointers）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---