题目描述

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

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

输入描述:

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

输出描述:

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

输入例子:

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

输出例子:

8

思路

将输入的数用sort()进行排序，然后用双循环从头到尾和从尾到头进行题目要求的比较，满足要求就计数。即对数组先进行排序（升序），以样例来说，排序完后，顺序为：1,2,3,4,5,6,7,8,9,20；那么选择v[0]为最小数，乘p，那么可以取的M的可以为1,2,3,4,5,6,7,8。一共有8个，假如进行第二次遍历，从v[1]开始，那么可以选择便有2,3,4,5,6,7,8,9，共有8个。我们只需要这样遍历便可以得到最长的完美数列。

C

 1 #include <stdio.h>
 2 int cmp(const void * a, const void * b) {
 3     return *(long int *)a - *(long int *)b;//升序
 4 }
 5 int main() {
 6     int N, max = 0;//正整数个数, 完美数列最多含有的数字个数 
 7     long int p;//参数p 
 8     scanf("%d %ld", &N, &p);
 9     long int arr[N];
10     for (int i = 0; i < N; i++) {
11         scanf("%ld", &arr[i]);
12     } 
13     qsort(arr, N, sizeof(long int),cmp);//升序排序
14     for (int i = 0; i + max <= N; i++) {// 数列未取完
15         for (int j = i + max; j < N; j++) {// 超过完美数列数字个数，是否为完美数列
16             if(arr[j] <= (arr[i] * p)) {
17                 max = j - i + 1;
18             } else {//如果不是，后续元素更大，更不可能是，跳出循环即可
19                 break;
20             }
21         } 
22     }
23     printf("%d\n", max);
24     return 0;
25 }

 

Java

 1 import java.util.Scanner;
 2 import java.util.Arrays;
 3 public class Shulie01 {
 4     public static void main(String[] args) {
 5          @SuppressWarnings("resource")//这句是装饰，为了美观
 6         Scanner in=new Scanner(System.in);
 7         int n = in.nextInt();//输入第一个数
 8         int p = in.nextInt();//输入第二个数
 9         int[] arr = new int[n];//定义一个一维数组
10         for(int i = 0;i<n;i++)//遍历循环输入
11             arr[i] = in.nextInt();
12         Arrays.sort(arr);//对数组进行从小到大排序
13         int maxlen = 0;//计数变量
14         for(int i = 0;i<n;i++){//i从0开始依次递加作外层循环，a[i]为最小值
15             for(int j = i+maxlen;j<n;j++){//最大值从最小值位置加上当前完美数列最多元素个数处开始，a[j]为最大值
16                 if(arr[j]>arr[i]*p) {//如果不符合完美数列，跳出循环
17                     break;
18                    }
19                 maxlen++;//符合条件计数
20             }
21         }
22         System.out.println(maxlen);//输出最多可以选择多少个数可以用它们组成一个完美数列
23     }
24 }

 

JAVA中sort函数的使用方法

  • 在java.util.Collections类中有个sort()方法，主要是用来给数组排序，排序的规则可以自己重写。它是Arrays类的静态方法。
  • sort()函数的基本格式（默认排序为升序排序）。 
Arrays.sort(int[] a, int fromIndex, int toIndex)；即Arrays.sort(数组名,起始下标,终止下标);
  • 如果一个数组初始化时已经赋值。则sort函数可以另外一种格式 
Arrays.sort(数组名);
  • 如果读者不是很了解，可以暂时不去管它，如果真的很想了解，建议查阅我的推荐的一本书《Java从入门到经通》，上面有详细的介绍。

python

1.对最小值的选取从有序列表第一项开始循环；

2.在上述循环内对最大值的选取进行循环,保存此时的完美数列项数；

3.既然我们是为了获取完美数列项数最大值，那就注意，最大值所在内层循环可以优化：从最小值index加上完美数列项数形成下一次内层循环的最小index。

附：

#split() 通过指定分隔符对字符串进行切片，如果参数 num 有指定值，则分隔 num+1 个子字符串
#sorted() 函数可以对任意可迭代对象排序
 1 n,q = map(int, input().split())  # 获取数列长度n,完美数列所需比值q
 2 li = list(map(float, input().split()))  # 获取数列
 3 li.sort()  # 对数列排序
 4 m = 0  # 符合条件的完美数列长度，初始化为0
 5 for i in range(n):  # 完美数列最小项循环
 6     m_q = li[i] * q  # 完美数列最小项*q</span>
 7     next_ = i+m  # 完美数列最大项+1，作为内层完美数列最大项循环的下界
 8     if next_ >= n:  # 判断是否已达到数列末项
 9         break
10     for j in range(next_,n):  # 完美数列最大项循环</span>
11         if li[j] <= m_q:  # 第j项满足完美数列条件，则完美数列长度+1
12             m += 1
13         else:  # 最大值项达不到条件，推出循环
14             break
15 print(m)