pat1030完美数列(25) [two pointers]

给定⼀个正整数数列，和正整数p，设这个数列中的最⼤值是M，最⼩值是m，如果M <= m * p，则称这个数列是完美数列。

现在给定参数p和⼀些正整数，请你从中选择尽可能多的数构成⼀个完美数列。

输⼊格式：

输⼊第⼀⾏给出两个正整数N和p，其中N（<= 105）是输⼊的正整数的个数，p（<= 109）是给定的参数。第⼆⾏给出N个正整数，每个数不超过109。

输出格式：

在⼀⾏中输出最多可以选择多少个数可以⽤它们组成⼀个完美数列。

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

8

分析：⾸先将数列从⼩到⼤排序，设当前结果为result = 0，当前最⻓⻓度为temp = 0；从i = 0～n，j从i + result到n，【因为是为了找最⼤的result，所以下⼀次j只要从i的result个后⾯开始找就⾏了】每次计 算temp若⼤于result则更新result，最后输出result的值

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n;
	long long p;
	scanf("%d%lld", &n, &p);
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	sort(v.begin(), v.end());
	int result = 0, temp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + result; j < n; j++) {
			if (v[j] <= v[i] * p) {
			temp = j - i + 1;
			if (temp > result)
			result = temp;
			} else {
				break;
			}
		}
	}
	cout << result;
	return 0;
}

---

本系列(PAT算法)作者mail：1302304703@qq.com(非本人)