[PAT B1030/A1085]Perfect Sequence_综合

[PAT B1030/A1085]Perfect Sequence

本题是PAT乙级1030题和甲级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.

输入格式

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10?⁵??) is the number of integers in the sequence, and p (≤10?⁹??) is the parameter. In the second line there are N positive integers, each is no greater than 10?⁹??.

输出格式

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

输入样例

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

输出样例

--------------------------中文原题---------------------------

题目描述

1030 完美数列（25 分)给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mxp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式

输入第一行给出两个正整数 N 和 p，其中 N（≤10?⁵??）是输入的正整数的个数，p（≤10?⁹??）是给定的参数。第二行给出 N 个正整数，每个数不超过 10?⁹??。

输出格式

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

解析

本题不算是一道很难的题目，但是要想做到拿满分确实不简单，首先如果是用简单的暴力枚举，那么时间复杂度会高达O(n^2)，必然会有数据过不了，由于我们按升序排列后数列是有序的，那么我们在检查一组数之后，对于下一个数据，我们可以从上次查找后的最后一个数据的下一个数据开始，这样就能简化代码了。
如果不想那么麻烦的话，我们可以考虑使用algorism头文件中的upper_bound函数，这个函数的功能是返回第数组中第一个大于某元素的地址，非常的方便。
此外这个题目最需要注意的一点就是，由于每个数和p最多是10⁹级别的，两者相乘最多可以达到10¹⁸，用int是装不下的，为了避免出错，索性所有的数据都用long long存储，这样不需要考虑某个地方转换啊什么的，非常方便。
解法一：

#include<iostream>
#include<algorithm>
using namespace std;
int num[100010] = {
     0 };
int main()
{
    long long n, p;scanf("%ld%ld", &n, &p);for (int i = 0; i < n; i++) scanf("%ld", &num[i]);sort(num, num + n);  //排序int cnt = 0, max = 0;for (int i = 0; i < n; i++) {
    long long up_bound = num[i] * p;for (int j = i + cnt; num[j] <= up_bound&&j < n; j++) cnt++; //这里往后找一位，就使cnt++if (cnt > max)max = cnt;if (i + cnt >= n)break;cnt--; //因为下一步i++了，所以相应的下一个数的cnt--}printf("%d", max);return 0;
}

解法二：

#include<iostream>
#include<algorithm>
using namespace std;
int num[100010] = {
     0 };
int main()
{
    int n, p;scanf("%d%d", &n, &p);for (int i = 0; i < n; i++) scanf("%d", &num[i]);sort(num, num + n);int max = 1;for (int i = 0; i < n; i++) {
    long long up = num[i] * p;int j = upper_bound(num + i + 1, num + n, up) - num;if (j - i > max) max = j - i;}printf("%d", max);return 0;
}

[PAT B1030/A1085]Perfect Sequence