PAT(B) 1030 完美数列 - C语言 - 滑动窗口 & 双指针

题目链接:1030 完美数列 (25 point(s))

给定一个正整数数列,和正整数 \(p\),设这个数列中的最大值是 \(M\),最小值是 \(m\),如果 \(M≤mp\),则称这个数列是完美数列。

现在给定参数 \(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

题解

如果用双层循环的话,肯定是会超时的。

需要先排序。再用滑动窗口(双指针)来解决此题。

不断移动右边界。然后用左边界向右移动不断试探。并记录最大值。

示例过程如下:
1、先升序排序

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

2、两个指针 \(left\) 和 \(right\) 指向第一个数据,最大长度 \(maxLen = 0\)

1 2 3 4 5 6 7 8 9 20
\(left\)
上一篇:CentOS 6.4出现Disk sda contains BIOS RAID metadata解决方法 jajavaja的专栏


下一篇:使用Python解析JSON详解