首页 > 试题广场 >

完美数列(25)

[编程题]完美数列(25)
  • 热度指数:30582 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个数列是完美数列。



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

输入描述:
输入第一行给出两个正整数N和p,其中N(<= 105)是输入的正整数的个数,p(<= 109)是给定的参数。第二行给出N个正整数,每个数
不超过109


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

输入

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

输出

8
头像 select*fromuse
发表于 2019-12-03 15:18:36
分析 这道题目首先需要考虑选择尽可能多的数构成一个完美数列。而它的条件又仅需要最大,最小值参与,比较能联想到需要用到排序,接下来按照循环去做。 优化 不考虑排序,仅考虑这个循环查找算法,它的时间复杂度达到了,如何优化它是接下来考虑的问题。这里有介绍两个方法二分查找和双指针法。 二分查找 展开全文