PAT A1085 Perfect Sequence(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1085 Perfect Sequence
中文版:B1030 完美数列

解题思路

对数字进行排序,设定两个“指针 i 和 j ”分别为完美数列的头和尾,在数组中不断移动“指针”并记录当前完美数列长度,个数正好为 j - i + 1,同时更新完美数列最大长度。

易错点

  • $m * p$ 可能越界,所以要用 long long 进行类型转换

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
int N, p, S[100010];
scanf("%d %d", &N, &p);
for(int i = 0; i < N; i++){
scanf("%d", &S[i]);
}
sort(S, S + N);
int cnt_max = -1;
for(int i = 0, j = 0; i < N; i++){
while(j < N && S[j] <= (long long )S[i] * p){
cnt_max = max(j - i + 1, cnt_max);
j++;
}
}
printf("%d\n", cnt_max);
return 0;
}