完美数列(25)

[编程题]完美数列(25)

热度指数：30582 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。

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

输入描述:

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

输出描述:

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

示例1

输入

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

输出

算法知识视频讲解

Python

_skc_

为什么错了啊

N, p = list(map(int, input().split()))
group = list(map(int, input().split()))
group.sort()
k = 1
for i in range(0, N):
    if i + k >= N:
        break
    if group[i+k] > group[i] * p:
        break
    for j in range(i+k, N):
        if group[i] * p >= group[j]:
            k += 1
        else:
            break
print(k)

发表于 2021-07-06 22:27:00 回复(0)

Python

棠荼

[n,p]=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
Max=0
l=0
while a[-1]>a[l]*p:
      l=l+1
if len(a)-l>Max:
      Max=len(a)-l
x=len(a)-2
while l!=0 and x>=0:
      while a[x]<=a[l]*p and l>=0:
            l=l-1
      l=l+1
      if x-l+1>Max:Max=x-l+1
      x=x-1
print(Max)

python的解法↑

发表于 2019-09-07 15:45:47 回复(0)

Python

北风扬尘尘飞扬

差评，严重差评>>>
最后一个用例一直不通过，
发现是这个缘故:
对于以下测试:最佳应该是1,2,3,4
这与题目直接得出的结果2不符。。。
6 4
1 2 3 4 5 18
即实际上寻址的是最大子序列，而非从右端最大值开始找。
代码如下:

# -*- coding : utf-8 -*-
result = 0
n, p = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
count = 0
for i in range(len(nums)):
    for j in range(i + count, len(nums)):
        if nums[j] > p * nums[i]:
            break
        count += 1
print(count)

发表于 2019-05-30 01:23:21 回复(0)

Python

qswhy

while True:
    try:
        num,p = list(map(int,input().split()))
        digits = list(map(int,input().split()))
        digits.sort()
        theMaxNum = 0
        for i in range(num):
            for j in range(i+theMaxNum,num):
                if digits[j] > digits[i]*p:
                    break
                theMaxNum += 1          
        print(theMaxNum)
    except Exception:
        break

发表于 2019-03-08 10:38:46 回复(0)

Python

TimeMac

参考亿水寒的Python版。就十行代码
之前自己的思路是从两端找，两个指针a,b，比较MAX/MIN<=p;最大的往左移，最小的往右移，谁的变化大就移动谁。
比较MAX[a]/MAX[a-1] 和MIN[b+1]/MIN[b]谁的变化大。时间复杂度O(n),可不曾料到测试用例里含有相同数，方法完全失败。~~~~(>_<)~~~~

while True:
    try:
        num,p = list(map(int,input().split()))
        digits = list(map(int,input().split()))
        digits.sort()
        theMaxNum = 0
        for i in range(num):
            for j in range(i+theMaxNum,num):
                if digits[j] > digits[i]*p:
                    break
                theMaxNum += 1           
        print(theMaxNum)
    except Exception:
        break

编辑于 2018-09-22 10:14:27 回复(0)

Python

WilliamY

问大神们一个问题，下面的代码用python2超时，用python3可以通过，为什么？

#python2
n, p = [int(x) for x in raw_input().strip().split()]
arr = [int(x) for x in raw_input().strip().split()]
arr.sort()

maxlen = 0
for i in range(n):
  for j in range(i+maxlen, n):
    if arr[i] * p < arr[j]:
        break
    maxlen = maxlen + 1
print (maxlen)

#python3
n, p = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
arr.sort()

maxlen = 0
for i in range(n):
  for j in range(i+maxlen, n):
    if arr[i] * p < arr[j]:
        break
    maxlen = maxlen + 1
print (maxlen)

发表于 2017-08-07 15:31:28 回复(1)