1020完美数列解题方式
题目
给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;bool cmp(int a, int b) {return a < b;
}void func(int a[], int n, int p) {int num = 0;for (int i = 0; i < n; i++) {long m = p * a[i];int n1 = 0;for (int j = i; j < n; j++) {if (a[j] <= m) {n1++;}}if (cmp(num, n1))num = n1;}printf("%d", num);
}int main() {// freopen("in.in", "r", stdin);int n, p;scanf("%d %d", &n, &p);int a[n];for (int i = 0; i < n; i++) {scanf("%d",a+i);}sort(a, a + n, cmp);func(a, n, p);return 0;
}这题思路如果按照以上的解题方式简单，时间复杂度就是O(n^2)。
对于数组输入的方式，如果将scanf输入换成cin的输入方式，可能会出现超时的情况。这里放的解法是我想到的比较容易实现的。关于其他解法，我想到二分查找的方法，但是没有实现，卡在了中间数a[mid]和m*p那里，不知道怎么判断。
参考以下的文章，low返回的就是能够到达的最大数列中不超过m*p的数字的下表。这个也需要分析才能理解，对于题目使用的二分查找的方法时间复杂度为O(nlogn)
二分查找解题思路
参考文件的多种解法出处PAT-Basic 完美数列(25) 二分法和双指针c++解题思路_牛客网 (nowcoder.com)
/** app=PAT-Basic lang=c++* https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int N, p;
/* 二分法：* 注意数据边界，10^9很容易超过int范围，所以用long long*/
int binarySearch(int low,long long m){int high = N - 1;while (low <= high){int mid = low + (high - low) / 2;if (a[mid] <= m*p)low = mid + 1;elsehigh = mid - 1;}return low;
}
int main()
{scanf("%d%d", &N, &p);for (int i = 0; i < N; i++){scanf("%d",&a[i]);}sort(a,a+N);int maxNum = 0;for (int i = 0; i < N; i++){int low = binarySearch(i, a[i]);maxNum = low - i > maxNum ? low - i : maxNum;}printf("%d",maxNum);return 0;
}二分查找扩展
基于二分查找，可以进一步扩展两个方法。
-
查找第一个大于或等于x的元素位置
-
查找第一个大于x的元素位置
文章里面还有一种双指针方法解题思路：
双指针解题：
/** app=PAT-Basic lang=c++* https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int main()
{/*双指针法*/int N, p;long long mp;scanf("%d%d",&N,&p);for (int i = 0; i < N;i++){scanf("%d", &a[i]);}sort(a, a + N);int max = 0,high = 0;//high赋值一次即可for (int i = 0; i < N;i++){mp = (long long)a[i] * p;while (high < N){if (a[high] <= mp) high++;//对于后面的数来说，a[high]要么是第一个大于mp的数，要么是小于等于mp的数。else break;}max = max > high - i? max : high - i;}printf("%d",max);return 0;
}