1030 完美数列(two pointers解法)
1. 这道题出现在二分法，但是特殊之处在于，双指针是嵌套的，程序看上去有些像暴力枚举，但其实是利用了，如果i<j，a[i]*p>=a[j]，那么一定有k在[i,j]范围内，a[i]*p>=a[k]，以及a[k]*p>=a[j]，那么对于一个比较大的i来说，想获得更大的差值，j是不用比上一个比较小的i得到的j小了。这里的限制关系是双指针降低复杂度的原理。
2. 起初困惑为什么外层的while条件已经有了j<n，内层的while还是出现这个条件，是因为在进行内层的循环时，顾不上外层的这个条件，所以内层对j进行增加操作时需要再写一遍。
AC代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int maxn = 100010;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;LL Map[128];int A[maxn];int main(){int n,p;scanf("%d%d",&n,&p);for(int i=0;i<n;i++){scanf("%d",&A[i]);} sort(A,A+n);int i=0,j=0;int count = 0;while(i<n&&j<n){while(j<n&&(LL)A[i]*p>=A[j]){count = max(count,j-i+1);j++;}i++;}printf("%d",count);return 0;
}相关文章：
alsa声卡切换
环境 ubuntu12.04 因为桌面版的默认装了，而且调声音也很方便，这里说一下server版下的配置，毕竟做开发经常还是用server版的 1.安装 apt-get install alsa-base 它会把alsa-utils也一块装了，这是个工具包，如果没装的话 …
asp.net获取网站路径
网站在服务器磁盘上的物理路径: HttpRuntime.AppDomainAppPath 虚拟程序路径: HttpRuntime.AppDomainAppVirtualPath 任何于Request/HttpContext.Current等相关的方法, 都只能在有请求上下文或者页面时使用. 即在无请求上下文时,HttpContext.Current为null. 而上面提到的方法一…
iOS 绘制圆角
级别： ★☆☆☆☆ 标签：「iOS切圆角」「layer圆角」「CAShapeLayer圆角」 作者： XsH 审校： QiShare团队 项目中会常有圆角（或圆形）显示视图的需求（比如用户头像的显示），也…
(C++)归并排序的递归与非递归实现
递归实现 merge函数利用的是双指针技巧降低复杂度。 mergeSort函数使用了递归，当中先对左右序列各调用一次mergeSort，再对整个序列调用merge。就按照最浅层的归并的思想去理解，不要大脑走到哪就step in。 另外mergeSort进入递归有个left&l…
SnackbarUtilDemo【Snackbar的封装类】
版权声明：本文为HaiyuKing原创文章，转载请注明出处！ 前言 这个工具类参考的是《没时间解释了，快使用Snackbar!——Android Snackbar花式使用指南》，代码几乎一样，所以想要了解具体原理或者更详细信息请阅读…
java通过代理访问网络
使用代理方式连接到网络 Testpublic void t13(){String charset "utf-8" ; String proxyHost "代理地址" ; int proxyPort 1234 ; //代理端口String proxyUrsername "登陆代理服务器的用户名" ; String proxyPassword "登陆代理服务器…
poj2503 Babelfish
跟poj3349很类似的题目，这题还稍简单。用qsort快速排序和二分查找可以很轻松AC。以下是代码： Run IDUserProblemResultMemoryTimeLanguageCode LengthSubmit Time5135234zen_chou2503Accepted2356K547MSC1212B2009-05-11 20:12:26Code1 #include <std…
(C语言)一种简易记法：生成[a,b]范围内的随机整数
1. 添加头文件 #include<stdlib.h> #include<time.h> 2. 初始化随机种子 srand((unsigned)time(NULL)); 3. 确定元素个数b-a1，以及最小元素 printf("%d",rand()%(b-a1)a);//生成[a,b]之间的数 printf("%d",rand()%1001);//生成…
IE和火狐都支持的方法(输入用户名和密码后按下 enter 键)
在Firefox中老报"event is not defined”错误！原因是因为在Firefox中使用了不同的事件对象模型,不同于IE Dom，用的是W3C Dom。 document.οnkeydοwnfunction mykeyDown(e){ //compatible IE and firefox because there is not event in fir…
数据库中存储与读取文件
if exists (select * from dbo.sysobjects where id object_id(N[dbo].[p_binaryIO]) and OBJECTPROPERTY(id, NIsProcedure) 1)drop procedure [dbo].[p_binaryIO]GO /*--bcp 实现二进制文件的导入导出 支持image,text,ntext字段的导入/导出 image适合于二进制文件,包括:Wor…
洛谷P3723 [AH2017/HNOI2017]礼物（FFT）
传送门 首先，两个数同时增加自然数值相当于只有其中一个数增加（此增加量可以小于0） 我们令$x$为当前的增加量，${a},{b}$分别为旋转后的两个数列，那么$$ans\sum_{i1}^n(a_ix-b_i)^2$$ 然后把第$i$项提出来并展开&#x…
1035 插入与归并
1. 这一题，首先要会插入排序和归并排序的写法。对于归并排序，可以用非递归sort最简便。把每一趟的结果存进二维数组。 2. 单独封装一个函数，比较两个一维数组是否完全一样。 3. 由于归并比插入的复杂度低，趟数少，所以…
代码设置LinearLayout的高度
问题描述我想把这个LinearLayout宽度设置成为FILL_PARENT，源码如下LinearLayout checkboxLinearLayout (LinearLayout) getLayoutInflater().inflate(R.layout.checkboxdoitem, null);LayoutParams params (LayoutParams) checkboxLinearLayout.getLayoutParams();…
精通Spring Boot —— 第十五篇：使用@ControllerAdvice处理异常
在Spring 3.2中，新增了ControllerAdvice、RestControllerAdvice 注解，可以用于定义ExceptionHandler、InitBinder、ModelAttribute，并应用到所有RequestMapping、PostMapping， GetMapping注解中。接下来我将通过代码展示如何使用这…
架构设计之分布式文件系统
1：类图 2：数据结构 create table TBCOFILE ( FILEID INTEGER not null, FILETIME DATE, TYPE VARCHAR2(10), USERID INTEGER, IP VARCHAR2(20), APPTYPE INTEGER default 0) 3：开发步骤 1：从数据库申…
1029 Median
1. 开始测试点3和6答案错误，原因是没有考虑到，给的两个数列有可能长度相差很大，某个数列还没到中位数，就结束了。 2. 这题的底子是用two pointers按照非递减的顺序合并两个数列，无非是再确定一下中间那个数的下标&…
理解系统底层的概念是多么重要
理解系统底层的概念是多么重要 ——趋势科技邹飞评《程序员的自我修养》 关于《程序员的自我修养》这本书，最初是在和博文的周筠老师MSN上谈起，当时听周老师提及这本书是一本关于链接和装载等系统软件知识的书籍，当时就很感兴趣，因…
session删除
删除一个session值： session_unset(变量); session_destroy(变量); 删除一个cookie： 注意第二个参数中手册中的说明是： Cookie 必须用和设定时的同样的参数才能删除。如果其值一个空字符串，或者是 FALSE，并且其它的参数…
Android学习路线
Android学习路线 第一阶段：Java面向对象编程 1.Java基本数据类型与表达式，分支循环。 2.String和StringBuffer的使用、正则表达式。 3.面向对象的抽象，封装，继承，多态，类与对象，对象初始化和回…
1048 Find Coins(two pointers解法)
1. 很典型的双指针的应用，将数组按照非降排列，两个指针从一头一尾开始包抄，若等于（等于要放在第一个）则返回结果结束程序，小于则左指针右移，大于则右指针左移。 2. 起初还担心，如果…
TCP/IP 协议理解
TCP/IP 协议（Transmission Control Protocol / internet Protocol），因特网互联协议，又名网络通讯协议。通俗而言：TCP负责发现传输的问题，一有问题就发出信号，要求重新传输，直到所有数…
Webhint开源了一种代码检查工具
Webhint项目提供了一种用于检查代码的可访问性、性能和安全的开源检查（Linting）工具。在创建Web站点和应用中，有越来越多的细节问题亟待完善。为此，Webhint力图帮助开发人员标记这些细节。\\Webhint以命令行接口（CLI&a…
SHAREPOINT爬网设置
F:\2009年\MOSS档案 http://share:30088/default.aspx 进入管理中心 共享服务管理-SharedServices1-搜索设置-内容源和爬网计划-本地 Office SharePoint Server 网站-下拉- -编辑-爬网计划-完全(增量)爬网-创建计划 - 对该内容源启动完全爬网-勾选上。 一、 爬网设置ÿ…
1093 Count PAT‘s
这题出现在“活用递推”专题下面，所谓递推就是这一步的结果和上一步的结果有直接联系。对于本题来说，从左到右，记到当前位置，一共出现的P的个数，如果当前位置是P，则个数就是上一位的加1，否则等于…
拜托，面试别再问我时间复杂度了！！！
最烦面试官问，“为什么XX算法的时间复杂度是OO”，今后，不再惧怕这类问题。 快速排序分为这么几步： 第一步，先做一次partition； partition使用第一个元素tarr[low]为哨兵，把数组分成了两个半区&a…
C#和JavaScript的简单互交
转自：http://cgxcn.blog.163.com/blog/static/132312422009426112558831/ 1.asp.net呼叫js Response.Write("<script languagejavascript>"); Response.Write("alert(登峰欢迎您 );" ); …
读阮一峰对《javascript语言精粹》的笔记，我有疑问。
《javascript语言精粹》是一本很棒的书籍，其中作者在附录列出了12种他所认为的javascript语言中的糟粕。 我最近开始跟读前端前辈的博客，其中读到了阮一峰的《12种不宜使用的Javascript语法》，有一个疑问： 文如下： 9. …
1008 Elevator
思路如下：用一个整型数组存楼层，0号元素为0(开始停在0层)，每读入一个元素，和上一个比较，更大说明是上升，总时长加上楼层差*6，反之说明是下降，总时长加上楼层差*4。最后再管停留时间&…
软件安全性能測试（转载）
近来，在我负责的公司某软件产品的最后測试工作，经常被问到这样一个问题：在做測试过程中，我们的软件产品在安全性方面考虑了多少？应该怎样測评一个软件究竟有多安全？ 这个软件因为涉及客户商业上重要的…
org.springframework.data.redis 一次连接获取特定key所有k-v(pipeline）
2019独角兽企业重金招聘Python工程师标准>>> 当我们需要一次性获取在redis中以hash方式存储的所有key-value时，我们可以使用下面的方式来获取。 public void testGetMore() throws IOException {RedisCallback<List<Object>> pipelineCallba…