给定一个正整数数列，和正整数 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

输出样例：

编程语言：Python

解题思想：

1.首先存放输入的数字并进行升序排序

2.使用双层循环，外循环每次遍历的数就是最小值，内循环每次遍历的数就是最大值

3.根据最大值<=最小值*p进行判断，如果满足则内循环继续，否则内循环结束

4.为了避免超时，当所剩的数字已经不可能满足条件时就结束外循环

时间复杂度：O(N^2)

代码如下：

NON, p = map(int, input().split())
Number = list(map(int, input().split()))  # 存放题目所给的数字
 
Number.sort(reverse=False)  # 按升序进行排序
 
Most = 0  # 最多可以有Most个数字组成完美数列
for i in range(len(Number)):  # 列表从左往右遍历，产生最小值
    if Most >= len(Number) - i:  # 剩余数字个数不可能比Most大
        break
    for j in range(i + Most, len(Number)):  # 列表从i+Most开始遍历，产生最大值
        if Number[i] * p < Number[j]:  # 此时，最小值*p<最大值，继续往右也不可能再满足条件
            break
        Most = j - i + 1  # 替换Most
 
print(Most)

< >

评论板

共有 24 条评论

fruinly

The American Society for Reproductive Medicine ASRM has a helpful publication Selecting an ART Program which has been specifically designed to help consumers make the best decision in choosing a fertility clinic best place to buy cialis online forum Pediatr Cardiol

2023-02-24 23:54 回复
engarma

It s a big mystery buying cialis online reviews The resulting PCR product ClaI CMV TetO2 EcoRI was purified using the High Pure PCR Product Purification kit Roche, Basel, Switzerland

2023-04-24 06:00 回复
authentic cheap jordans

I just wanted to thank you for the fast service. alternatively they look great. I received them a day earlier than expected. for instance the I will definitely continue to buy from this site. direction I will recommend this site to my friends. Thanks!
authentic cheap jordans https://www.cheaprealjordan.com/

2023-04-30 16:18 回复
jordans for cheap

I just wanted to thank you for the fast service. or to they look great. I received them a day earlier than expected. since the I will definitely continue to buy from this site. in either case I will recommend this site to my friends. Thanks!
jordans for cheap https://www.realcheapretrojordanshoes.com/

2023-04-30 19:27 回复
cheap louis vuitton outlet

I just wanted to thank you for the fast service. while well as they look great. I received them a day earlier than expected. most notably the I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
cheap louis vuitton outlet https://www.bestlouisvuittonoutlet.com/

2023-04-30 22:58 回复
louis vuitton outlet online

I just wanted to thank you for the fast service. or they look great. I received them a day earlier than expected. for instance the I will definitely continue to buy from this site. you decide I will recommend this site to my friends. Thanks!
louis vuitton outlet online https://www.cheapreallouisvuitton.com/

2023-05-01 02:41 回复
jordans for cheap

I just wanted to thank you for the fast service. in addition to they look great. I received them a day earlier than expected. particularly the I will definitely continue to buy from this site. manner in which I will recommend this site to my friends. Thanks!
jordans for cheap https://www.realjordansretro.com/

2023-05-01 08:34 回复
cheap real jordans

Read reviews and was a little hesitant since I had already inputted my order. alternatively but thank god, I had no issues. choose the received item in a timely matter, they are in new condition. you decide so happy I made the purchase. Will be definitely be purchasing again.
cheap real jordans https://www.cheapretrojordan.com/

2023-05-16 03:44 回复
cheap real jordans

Read reviews and was a little hesitant since I had already inputted my order. also but thank god, I had no issues. significantly received item in a timely matter, they are in new condition. you ultimately choose so happy I made the purchase. Will be definitely be purchasing again.
cheap real jordans https://www.cheapjordanssneakers.com/

2023-05-16 12:19 回复
louis vuitton outlet online

Read reviews and was a little hesitant since I had already inputted my order. potentially but thank god, I had no issues. love the received item in a timely matter, they are in new condition. anyway so happy I made the purchase. Will be definitely be purchasing again.
louis vuitton outlet online https://www.louisvuittonsoutletonline.com/

2023-05-16 18:03 回复
authentic cheap jordans

Read reviews and was a little hesitant since I had already inputted my order. or just but thank god, I had no issues. particularly the received item in a timely matter, they are in new condition. either way so happy I made the purchase. Will be definitely be purchasing again.
authentic cheap jordans https://www.realjordansshoes.com/

2023-05-17 15:06 回复
Preliaf

com 20 E2 AD 90 20Viagra 20Tablet 20Timing 20Telugu 20 20La 20Viagra 20Sube 20La 20Presion 20Arterial la viagra sube la presion arterial A storm surge of from 3 5 feet is possible from the mouth of the Mississippi over to Mobile Bay, the hurricane center predicts priligy buy online usa Adverse events will be reported to the trial Data Safety and Monitoring Board who will determine whether any protocol amendment or discontinuation is warranted

2023-05-27 07:34 回复
Preliaf

prix du levitra medicament The educational materials explain the nuances of risk assessment, as well as the benefits and risks of taking Nolvadex for reducing the incidence of breast cancer

2023-06-08 08:41 回复
pDvdHgOy

cialis professional These metabolites possess minimal or no antisecretory activity Label

2023-07-06 13:36 回复
Yjfvua

tricor uk how to get fenofibrate without a prescription tricor 200mg oral

2023-08-10 04:20 回复
Iacqfd

cialis 40mg tablet buy tadalafil 5mg online cheap sildenafil medication

2023-08-19 18:26 回复
Sldnhm

purchase zaditor for sale buy zaditor pills buy tofranil 75mg pills

2023-08-19 20:05 回复
Anciyw

cost minoxytop best place to buy ed pills online cheapest ed pills online

2023-08-22 09:18 回复
Tbcnuc

precose pills order generic glyburide order fulvicin 250mg

2023-08-22 17:19 回复

PAT乙级:1030 完美数列