神码ai智能写作网站,网站改版换了域名,惠州网络营销公司,广西最优秀的品牌网站建设公司1030 完美数列 #xff08;25 分#xff09;给定一个正整数数列#xff0c;和正整数 p#xff0c;设这个数列中的最大值是 M#xff0c;最小值是 m#xff0c;如果 M≤mp#xff0c;则称这个数列是完美数列。 现在给定参数 p 和一些正整数#xff0c;请你从中选择尽可能…1030 完美数列 25 分 给定一个正整数数列和正整数 p设这个数列中的最大值是 M最小值是 m如果 M≤mp则称这个数列是完美数列。 现在给定参数 p 和一些正整数请你从中选择尽可能多的数构成一个完美数列。 输入格式 输入第一行给出两个正整数 N 和 p其中 N≤105是输入的正整数的个数p≤109是给定的参数。第二行给出 N 个正整数每个数不超过 109。 输出格式 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。 输入样例 10 8
2 3 20 4 5 1 6 7 8 9输出样例 8思路 先对数列进行排序然后枚举左端点也就是最小值m然后查找一个尽可能大的右端点M使得Mm*p,由于数列已经排序所以可以使用二分查找。upper_bound()返回第一个大于待查找元素的数列元素的下标如果没有找到返回第n个元素不存在所以需要进行返回值判断。注意点是m*p会超过int。code 1:手写二分 #includeiostream
#includestring
#includevector
#includestring
#includecstdio
#includecmath
#includestring.h
#includealgorithm
#includeunordered_map
#includestack
using namespace std;int main()
{int n,p;scanf(%d%d,n,p);long long int a[n];for(int i0;in;i)scanf(%lld,a[i]);sort(a,an);int maxv0;for(int i0;in;i){int lefti,rightn-1,ans-1;while(leftright){int midleft(right-left)/2;if(a[mid]a[i]*p){ansmid;leftmid1;}elserightmid-1;}if(ans!-1)maxvmax(maxv,ans-i1);}coutmaxv;return 0;
} code2 使用库函数 #includeiostream
#includestring
#includevector
#includestring
#includecstdio
#includecmath
#includestring.h
#includealgorithm
#includeunordered_map
#includestack
using namespace std;int main()
{int n;long long p;scanf(%d%lld,n,p);long long int a[n];for(int i0;in;i)scanf(%lld,a[i]);sort(a,an);int maxv0;for(int i0;in;i){int indexupper_bound(ai,an,a[i]*p)-a;if(indexn)index--;while(a[index]a[i]*p) index--;maxvmax(maxv,index-i1);}coutmaxv;return 0;
} 转载于:https://www.cnblogs.com/zhanghaijie/p/10406416.html
