1030 完美数列 (25 分)C、Java、python
2024-10-08 05:14:41
题目描述
给定一个正整数数列,和正整数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
#include <stdio.h>
int cmp(const void * a, const void * b) {
return *(long int *)a - *(long int *)b;//升序
}
int main() {
int N, max = ;//正整数个数, 完美数列最多含有的数字个数
long int p;//参数p
scanf("%d %ld", &N, &p);
long int arr[N];
for (int i = ; i < N; i++) {
scanf("%ld", &arr[i]);
}
qsort(arr, N, sizeof(long int),cmp);//升序排序
for (int i = ; i + max <= N; i++) {// 数列未取完
for (int j = i + max; j < N; j++) {// 超过完美数列数字个数,是否为完美数列
if(arr[j] <= (arr[i] * p)) {
max = j - i + ;
} else {//如果不是,后续元素更大,更不可能是,跳出循环即可
break;
}
}
}
printf("%d\n", max);
return ;
}
Java
import java.util.Scanner;
import java.util.Arrays;
public class Shulie01 {
public static void main(String[] args) {
@SuppressWarnings("resource")//这句是装饰,为了美观
Scanner in=new Scanner(System.in);
int n = in.nextInt();//输入第一个数
int p = in.nextInt();//输入第二个数
int[] arr = new int[n];//定义一个一维数组
for(int i = 0;i<n;i++)//遍历循环输入
arr[i] = in.nextInt();
Arrays.sort(arr);//对数组进行从小到大排序
int maxlen = 0;//计数变量
for(int i = 0;i<n;i++){//i从0开始依次递加作外层循环,a[i]为最小值
for(int j = i+maxlen;j<n;j++){//最大值从最小值位置加上当前完美数列最多元素个数处开始,a[j]为最大值
if(arr[j]>arr[i]*p) {//如果不符合完美数列,跳出循环
break;
}
maxlen++;//符合条件计数
}
}
System.out.println(maxlen);//输出最多可以选择多少个数可以用它们组成一个完美数列
}
}
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() 函数可以对任意可迭代对象排序
n,q = map(int, input().split()) # 获取数列长度n,完美数列所需比值q
li = list(map(float, input().split())) # 获取数列
li.sort() # 对数列排序
m = 0 # 符合条件的完美数列长度,初始化为0
for i in range(n): # 完美数列最小项循环
m_q = li[i] * q # 完美数列最小项*q</span>
next_ = i+m # 完美数列最大项+1,作为内层完美数列最大项循环的下界
if next_ >= n: # 判断是否已达到数列末项
break
for j in range(next_,n): # 完美数列最大项循环</span>
if li[j] <= m_q: # 第j项满足完美数列条件,则完美数列长度+1
m += 1
else: # 最大值项达不到条件,推出循环
break
print(m)
最新文章
- yii2使用小知识(连续补充)
- 【转载】 Java线程面试题 Top 50
- 启用CentOS6.5 64位安装时自带的MySQL
- 自定义HttpModule的一些经验--配置篇
- 学习zepto.js(Hello World)
- 数据结构之图 Part1
- JS实现星级评价
- DBGridEh 点击表头排序方法
- The 5th Zhejiang Provincial Collegiate Programming Contest---ProblemG:Give Me the Number
- 封装好的PHP分页类,简单好用--在开源看到的,取回来自己用
- HDU 2181 哈密顿绕行世界问题
- Git 常用命令速查表(图文+表格)
- Android开发概要记录
- Java Socket聊天室编程(二)之利用socket实现单聊聊天室
- codeforces 767C - Garland
- awk统计文件中某关键词出现次数
- JSP实现数据传递(web基础学习笔记三)
- Hadoop1.2.1 日志格式说明及启停方式
- codeforces833B The Bakery
- onkeypress、onkeydown、onkeyup