【PAT甲级 - C++题解】1085 Perfect Sequence

简介: 【PAT甲级 - C++题解】1085 Perfect Sequence

1085 Perfect Sequence


Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.


Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.


Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤105) is the number of integers in the sequence, and p (≤109) is the parameter. In the second line there are N positive integers, each is no greater than 109.


Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.


Sample Input:

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

Sample Output:

8


题意

给定一个正整数序列和常量 p ,假设一个序列的最小值为 m 以及最大值为 M ,那么当 m*p>=M 时,该序列为完美序列,现在需要我们找到给定序列中完美子序列的元素最大个数。


思路

具体思路如下:


1.存入每个元素,并对这些元素进行升序排序。

2.使用双指针进行完美子序列的查找,其中 i 表示上界即最大值,j 表示下界即最小值,然后用 for 循环从小到大遍历 i ,每趟遍历中 j 再从 0 开始递增,直至不满足 a[j]*p<a[i] 。计算当前序列个数 i-j+1 ,如果大于当前存储的答案 res ,则更新 res 。

3.输出答案 res 。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, p;
int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    //对数组进行排序
    sort(a, a + n);
    //双指针计算计算范围
    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        while ((long long)a[j] * p < a[i])  j++;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
296 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
378 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
359 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
329 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
253 0
|
C++
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
301 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
740 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
410 16