【PAT (Basic Level) 】1030 完美数列 (25 分)
给定一个正整数数列，和正整数 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
【输出样例】：
8
M≤mp
【AC代码1】：
#pragma warning(disable:4996)#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long ll;ll a[100005];int main()
{ll i, j, n, p;scanf("%lld%lld", &n, &p);for (i = 0; i < n; i++){scanf("%lld", &a[i]);}sort(a, a + n);i = 0;j = 0;ll ans = 1;while (i < n && j < n){while ((a[i] * p) >= a[j] && j < n){j++;}ans = max(ans, j - i);i++;}printf("%lld", ans);return 0;
}
【AC代码2】：二分法 upper_bound()
lower_bound upper_bound的用法
#pragma warning(disable:4996)#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long ll;ll n, p;
ll a[100005];int main()
{ll i;scanf("%lld%lld", &n, &p);for (i = 0; i < n; i++){scanf("%lld", &a[i]);}sort(a, a + n);ll r = 1;for (i = 0; i < n; i++){ll index = upper_bound(a + i, a + n, a[i] * p) - a;if (index == n)index--;while (a[index] > a[i] * p)index--;r = max(r, index - i + 1);}printf("%lld", r);return 0;
}
【AC代码3】：二分法 找到一个尽可能大的右端点M
#pragma warning(disable:4996)#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long ll;ll a[100005];int main()
{ll i, n, p;scanf("%lld%lld", &n, &p);for (i = 0; i < n; i++){scanf("%lld", &a[i]);}sort(a, a + n);ll r = 0;ll left, right, mid, ans;for (i = 0; i < n; i++){left = i;right = n - 1;ans = -1;while (left <= right){mid = (left + right) / 2;if (a[mid] <= a[i] * p){ans = mid;left = mid + 1;}else{right = mid - 1;}}if (ans != -1){r = max(r, ans - i + 1);}}printf("%lld", r);return 0;
}相关文章：
运营商劫持处理
测试URL：因近期发现长宽资源经常出现被劫持和转发错误的现象。解决办法如下：1、把转发列表写到named.conf文件里，更新我们的转发ip2、然后编写策略针对我们要去的域名从BGP出口出去，防止NAT。x.x.x.x.com，（…
oracle维护数据的完整性
转自：https://www.cnblogs.com/roger112/p/7722376.html 介绍： 数据的完整性用于确保数据库数据遵从一定的商业的逻辑规则。在oracle中，数据完整性可以使用约束、触发器、应用程序(过程、函数)三种方法来实现，在这三种方法中&…
MATLAB【五】———— matlab 调用C++生成exe文件，高斯核函数
两种方式调用C生成的exe文件， 语法： status system(command) [status,cmdout] system(command) [status,cmdout] system(command,-echo) 说明 status system(command) 调用操作系统执行指定的命令。操作会等待命令执行完毕，然后再将命令…
REACT day 1
https://facebook.github.io/react/ A JAVASCRIPT LIBRARY FOR BUILDING USER INTERFACES Declarative views make your code more predictable and easier to debug. React是Facebook在2013年发布的一个前端框架，而如今的React俨然已经演变成一个前端生态ÿ…
win10+Chrome浏览器截长图方法
本方法亲测可行，操作系统为win10，其他操作系统没有试过。 部分内容基于https://blog.csdn.net/ianly123/article/details/80565614并进行修正。 打开 Chrome 浏览器，进入需要截图的网站页面。打开开发者工具：在页面任何地方点击…
如何打造一流的视觉AI技术
本次分享主要分以下几个部分：首先简要介绍一下计算机视觉技术的相关背景，然后结合格灵深瞳的实践，从算法研发、训练平台、智能数据处理、异构计算等几个方面着重介绍如何打造一流的视觉AI技术，最后介绍格灵深瞳在相关技术落地方面…
MATLAB【六】 ———— matlab 随机散斑模拟
%% %input for image size(NX,NY) <散斑图大小（像素）> NX 1280; NY 800; %input for numble of speckles(S)<散斑数量> S 9226; %输入的散斑大小 a 4; %input for peak intensity of each speckle(I0)<散斑峰值强度> I0 1; %input …
【Python】zip函数
zip()函数用于将可迭代对象作为参数，将对象中对应的元素打包成一个个元组，然后返回这些由元组组成的列表。 如果各个迭代器的元素不一致，则返回列表长度与最短的对象相同。 利用*号操作符，可将元组解压为列表。 >>> a …
CentOS 7.0，启用iptables防火墙
CentOS 7.0默认使用的是firewall作为防火墙，这里改为iptables防火墙。1、关闭firewall：systemctl stop firewalld.service #停止firewallsystemctl disable firewalld.service #禁止firewall开机启动2、安装iptables防火墙yum install iptables-services…
手撸 webpack4.x 配置（一）
现在的前端开发框架 ，都绕不开 webpack 打包 。 但绝大数前端开发人员 基本都是用 脚手架 自动生成 一套开发环境 如： vue-cli , create-react-app等 , 但开发中总会遇到各种问题 ，基本都是 webpack 配置问题 ， 每次遇到基本都是…
MATLAB【七】———— matlab 高斯核使用，超像素图像模拟，矩阵转图像，深度相机模型实践实现
深度模型，图片转稀疏矩阵，稀疏矩阵转图片 %% mat to 2array temp_speckle ref_speckle; [row_index,col_index,v]find(temp_speckle); obj_matrix [row_index,col_index]; [obj_matrix_height,obj_matrix_width] size(obj_matrix);%% depth camera m…
jsp 出现cannot be resolved to a type问题解决办法
（1）检查<% page import>是否导入了相关的包。若是没有则需导入 （2）若导入相应的包后问题仍然存在则需创建相关的servlet转载于:https://www.cnblogs.com/wth21-1314/p/6126655.html
U盘中毒了？教你如何删除System Volume Information这个顽固文件夹
不得不说cmd命令很好用呢。最近我的U盘中毒了，格式化都删除不了System Volume Information这个顽固的文件夹，真心伤不起哇！还好现在解决了问题。看来以后得好好对待U盘，不能乱用了。本篇文章教大家如何删除System Volume Informat…
69亿美元英伟达史上最大收购！这家基金又赢了
。另一方面，在虚拟货币的浪潮告一段落之后，英伟达需要给增速放缓的数据中心业务注入一枚强心剂。 有意思的是，英伟达对Mellanox的收购也成就了国际知名维权对冲基金Starboard Value LP的又一次投资胜利。 击败微软、英特尔，交易…
基础数据结构【一】————数组
二维数组相乘，矩阵相乘， #include <iostream> using namespace std;void MatrixMultiply(int*, int*, int*, int, int, int); int main() {int M, N, P;int i, j;//矩阵A部分 cout << "请输入矩阵A的维数(M,N): " << endl;…
Fragment 和 FragmentActivity的使用
Fragment 和 FragmentActivity的使用 http://blog.csdn.net/izy0001989624/article/details/17072211转载于:https://www.cnblogs.com/as3lib/p/6126761.html
win10 VMware15 安装 CentOS6.4 64位（慢慢弄吧，别急）
参考：CentOS 6.4安装（超级详细图解教程） 可以都不勾，有需要，以后使用中有需要再手动安装 除了KDE，其他都选就可以了 系统管理、虚拟化、负载平衡器、高可用性可以都不选
Nginx网站常见的跳转配置实例
相信大家在日常运维工作中如果你用到nginx作为前端反向代理服务器的话，你会对nginx的rewrite又爱又恨，爱它是因为你搞定了它，完成了开发人员的跳转需求后你会觉得很爽，觉得真的很强大，恨它是因为当一些稀奇古怪跳转的需…
基础数据结构【二】————动态数组，单向链表及链表的反转
DEMO1： 动态分配变量（链表，而静态数组是线性表，意味着动态数组访问和遍历复杂度为O（n）,而插入和删除复杂度为O（1），而静态数组线性表则完全相反） int* in…
VMware15克隆虚拟机Centos
在克隆虚拟机之前，我们需要了解以下文件： 1、/etc/udev/rules.d/70-persistent-net.rules 这是网卡有关信息的配置文件，我们可以先查看一下master的网卡信息（当然也可以用ifconfig命令查看） 要注意的是网卡名称以及…
EXPDP 时ORA-27054 问题处置
现象：[oracleoracle1 ~]$ expdp xian/xian schemasxian directorydumpdir dumpfilexian.dmp LOGFILExian.logExport: Release 10.2.0.5.0 - 64bit Production on Friday, 02 December, 2016 20:19:48Copyright (c) 2003, 2007, Oracle. All rights reserved.Connec…
OSC源创会往期图文回顾链接地址收藏
为什么80%的码农都做不了架构师？>>> 格式：源创会报名链接地址 - 源创会结束后图文回顾链接地址 【深圳】第1期】- 图文回顾【广州】第2期】- 图文回顾【北京】第3期】- 图文回顾【珠海】第4期】- 图文回顾【深圳】第5期】- 图文回顾--------…
ionic + cordova+angularJs 搭建的H5 App完整版总结
为期半个月的项目实践开发，已完整告一段落，团队小组获得第一名，辛苦总算没有白费，想起有一天晚上，整个小组的人，联调到12点才从公司回去，真是心酸。这里总结一下，项目过程中遇到的问…
基础数据结构【三】————老鼠走迷宫问题————堆栈应用
假设：老鼠在一个二维地图中i行走，地图中大部分路径被墙阻断，无法前进。老鼠可以按照尝试错误的方法找到出口。只是，这只老鼠必须具备走错路时候就退回来，并且把走过的路记下来，避免下次走重复路，…
eclipse Debug中step into功能失灵的问题
step into 和 step over功能一样，无法进入方法内部，解决方法如下： 需要使用jdk中的jre，而不是独立安装的jre 再次Debug，当运行到断点的时候，点击step into（F5）就可以看见println函数…
Linux 基金会宣布红队项目，致力于孵化开源安全工具
百度智能云 云生态狂欢季 热门云产品1折起>>> 谁都想软件有着很高的安全性吧。毕竟，每一天都会有不一样的安全漏洞，从糟糕软件的沼泽中冒出来。 在近期举办的开源领导力峰会上，Linux 基金会宣布了新的红队项目（Red Tea…
基础数据结构【四】————环形链表与多项式
主要演示环形列表节点的创建插入， 删除，遍历，环形链表连接 。双向链表节点的建立与插入 ，双向链表中节点的删除 以及环形链表在多项式中的应用 DEMO1:环形链表节点的创建与插入 /* [名称]:ch03_08.cpp [示范]:环形链表节点的创…
关联scala源码
首先需要去官网下载sources 将下载好的压缩包拷贝到scala安装的lib目录下，解压 ctrlb以后 查看源码, 选择要查看的方法或者类, 输入 ctrl b import scala.io.StdIn 如果想看StdIn的源码，则将光标放在StdIn处，ctrlb 如果想查看io包下的内容&…
MySQL安装使用的2个问题
问题:1.遇到不输入密码能登上 ,使用密码报错.2.(解压版的) 在cmd输入>mysql –u root –p 时，按enter回车时，会叫你输入密码Enter password____,否则出现错误：ERROR 1045(28000):Access denied for user’root’’localhost’(using passw…
Flink1.7.2 sql 批处理示例
Flink1.7.2 sql 批处理示例 源码 https://github.com/opensourceteams/flink-maven-scala概述 本文为Flink sql Dataset 示例主要操作包括:Scan / Select,as (table),as (column),limit,Where / Filter,between and (where),Sum,min,max,avg,(group by ),group by having,disti…