PAT Basic 1030
2024-08-25 06:23:14
1030 完美数列
给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个数列是完美数列。
现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
输入格式:
输入第一行给出两个正整数N和p,其中N(<= 10^5^)是输入的正整数的个数,p(<= 10^9^)是给定的参数。第二行给出N个正整数,每个数不超过10^9^。
输出格式:
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例:
10 8
2 3 20 4 5 1 6 7 8 9
输出样例:
8
题解:这道题目看起来不难,但是N和P的数据量较大,导致需要使用long long int 进行计算,并且需要担心超时的问题。不过还好这道题给的
时间限制相对还是比较宽松的,只需要在暴力的基础上稍作修改就能跑过所有测试点。
暴力的话,自然就是先排序,然后写一个双重嵌套循环,然后找到符合条件的最大值即可,在此基础上,我们发现是要寻找最大值,那么每一次
我们只有在满足之前的最大值时,才进行这一次循环,即可减少时间复杂度,详见代码。
代码如下:
#include<iostream>
#include<algorithm>
using namespace std; int main()
{
long long int n, p, a[];
int result = ;
scanf("%lld %lld", &n, &p);
for( int i = ; i < n; i++) scanf("%lld",&a[i]);
sort(a,a+n);
for( int i = ; i < n; i++){
for( int j = i + result; j < n; j++){
if( a[j] > a[i]*p)
break;
if( j - i + > result)
result = j - i + ;
}
}
printf("%d",result);
return ;
}
最新文章
- hadoop运行原理之Job运行(四) JobTracker端心跳机制分析
- windosw应用提示内存不足
- Python复习笔记-字典和文件操作
- Javascript基础系列之(五)条件语句(switch语句)
- 关于iOS手势
- jquery递归遍历xml文件,形成ul-li序列,生成树结构(使用了treeview插件)
- ubuntu 默认 进入 命令行
- JavaWeb 文件上传 commons_fileupload方式
- URLScan安装及配置(转)
- Properties文件及与之相关的System.getProperties操作(转)
- ftp资源调用迅雷下载
- JS弹窗带遮蔽的功能
- 初级 Java 的 3 本进阶书
- 创建Git 仓库及 克隆、拉取、和推送操作
- Android 5.0以上Material Design 沉浸式状态栏
- Raspbian首次安装后无法使用SSH链接
- 查询在某一个时间段内的sql(oracel)
- react native项目的创建和运行
- 冲刺博客NO.4
- 【shell】创建长目录,目录存在则忽略,缺失则创建
热门文章
- “玲珑杯”ACM比赛 Round #4 E -- array DP
- mac 终端查看端口命令
- nodejs express session用法(含保存到redis)
- javascript for/forEach
- IP Addresses of Google Global Cache
- 微信公众号与HTML 5混合模式揭秘5——JSSDK开发技巧1
- IOS之constraints
- (一)mybatis之JDBC介绍
- shiro : java.lang.IllegalArgumentException: Odd number of characters.
- Python 解压序列、可迭代对象并赋值给多个变量