PAT B1083 是否存在相等的差(C++)

发表于 | 分类于 | |
字数统计: 335 字 | 阅读时长 ≈ 2 分钟
PAT甲级目录 | PAT乙级目录

题目描述

B1083 是否存在相等的差

解题思路

利用一个 hash 数组记录每个差出现的次数，最后倒序输出。

易错点

  • 只有出现次数大于 1 的差才被输出

也许陌生的知识点

  • map<int, int> m;
    • 用于映射，键和值可以是任意类型
    • 直接使用 m[<键>] = <值> 即可向map中添加一组键值对
    • 需要的头文件：map
  • for(auto it = m.begin(); it != m.end(); it++){}
    • 可用于遍历 map/vector/set 等容器， auto 实现自动匹配对应迭代器类型
    • 如果不用 auto it = m.begin() 则要写成 std::map<char, int>::iterator it = m.begin()
    • m.rbegin() 和 m.rend() 可实现逆向遍历
    • map<char,int> 在其他情况下可替换成对应元素的类型如 vector<int>
    • 包含该函数的容器： map / set / vector
  • it->first 和 it->second
    • it->first 为 map 中对应元素的关键字
    • it->second 为 map 中对应关键字的值
    • 所需头文件： map

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
int main(){
  int N, x;
  map<int, int> h;
  scanf("%d", &N);
  for(int i = 1; i <= N; i++){
    scanf("%d", &x);
    h[abs(x - i)]++;
  }
  for(auto it = h.rbegin(); it != h.rend(); it++){
    if((it->second) > 1) printf("%d %d\n", it->first, it->second);
  }
  return 0;
}