PAT A1085 Perfect Sequence(C++)

发表于 | 分类于 | |
字数统计: 215 字 | 阅读时长 ≈ 1 分钟
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;
}