共计 1769 个字符，预计需要花费 5 分钟才能阅读完成。
题目粗心：
从 N 个正整数中抉择若干个数, 使得选出的这些数中的最大值不超过最小值的 p 倍。问满足条件的抉择计划中，序列最长的长度是多少。
算法思路：
从 N 个正整数中抉择若干个数字组成一个序列，最大值为 M，最小值为 m，那么该序列中的数字，也就是从 m 到 M 的数字肯定是原序列中的间断序列，因为不然就会存在一个数字大于 m 小于 M 不在抉择的序列中，而后将其退出到该序列使其长度变大并且合乎题意，那么原来选出的序列就不是最长的了。所以咱们肯定是在一个有序序列中选出一个间断序列，使其最大值不超过最小值的 p 倍。为此，应用 nums 数组存储输出序列，而后将该序列进行排序，在有序序列中进行查找，这里给出 2 种查找的形式。
算法实现 1：
应用二分查找，这里借助 upper_bound 实现，该函数能够找到第一个大于待查找元素的地位 pos，如果不存在返回数组长度, 那么对于满足 m p>= M 的序列长度就为 pos 减去以后遍历元素的地位。而后每次都应用 ans 记录更大的长度。在 pos 为 N 的时候就没有必要持续往后查问了，因为肯定都满足 m p>=M，并且其长度肯定小于以后的序列长度
算法实现 2：
应用 2 个指针 i 和 j, 初始都指向 0，让 i 指向的元素为 m, 让 j 一值向后走，晓得第一次遇见 nums[i]p<nums[j]时进行，在 j 走动的过程中不断更新其长度 (应用 ans 保留) 而后在 j 进行后让 i 向后走一格,j 接着之前的地位向后持续走(没有从 0 开始向后走)，因为 m 增大的时候，小于 j 地位的元素都满足 nums[i]p>= 该元素。同样的在 nums[i]* p 大于序列中最大的元素 max_num 的时候就没有必要查问 j 了。
二分查找的函数阐明：
1、lower_bound(起始地址，完结地址，要查找的数值) 返回的是数值 第一个 呈现的地位。
2、upper_bound(起始地址，完结地址，要查找的数值) 返回的是 第一个大于待查找数值 呈现的地位。
3、binary_search(起始地址，完结地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool 值。
提交后果：
AC 代码 1：
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int N,p;
scanf("%d %d",&N,&p);
long long nums[N];
for (int i = 0; i < N; ++i) {scanf("%lld",&nums[i]);
}
sort(nums,nums+N);
long long ans = -1;
for (int j = 0; j < N; ++j) {long long m = nums[j];
// 找到第一个大于 m * p 的元素地位, 前一个地位就是满足 m *p>= M 的地位，并且该序列的长度最长
long long pos = upper_bound(nums+j,nums+N,m*p)-nums;
long long len = pos-j;
ans = ans>len?ans:len;
if(pos==N){
// 从 j 到 N - 1 的所有的元素都满足 m *p>=M, 无需再遍历后续元素了，其长度肯定比以后短
break;
}
}
printf("%lld",ans);
return 0;
}AC 代码 2：
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int N,p;
scanf("%d %d",&N,&p);
long long nums[N];
long long max_num = -1;
for (int i = 0; i < N; ++i) {scanf("%lld",&nums[i]);
max_num = max_num<nums[i]?nums[i]:max_num;
}
sort(nums,nums+N);
long long ans = -1;
int j=0;
for (int i=0;i<N;++i) {if(nums[i]*p>=max_num) {//nums[i]* p 大于序列中最大的元素 max_num, 无需再往后遍历了。ans = ans>N-i?ans:N-i;
break;
}
while (j<N){if(nums[i]*p<nums[j]){
// 找到第一个大于 m * p 的元素
break;
}
ans = ans>j-i+1?ans:j-i+1;
++j;
}
}
printf("%lld",ans);
return 0;
}
