PAT乙级1083 || 是否存在相等的差（详解，C/C++示例，测试点分析）

Posted on In

是否存在相等的差

题目描述

给定 N 张卡片，正面分别写上 1、2、……、N，然后全部翻面，洗牌，在背面分别写上 1、2、……、N。将每张牌的正反两面数字相减（大减小），得到 N 个非负差值，其中是否存在相等的差？

输入格式

输入第一行给出一个正整数 N（2 ≤ N ≤ 10 000），随后一行给出 1 到 N 的一个洗牌后的排列，第 i 个数表示正面写了 i 的那张卡片背面的数字。

输出格式

按照“差值 重复次数”的格式从大到小输出重复的差值及其重复的次数，每行输出一个结果。

输入样例

1
2
8
3 5 8 6 2 1 4 7

输出样例

1
2
3
5 2
3 3
2 2

问题解决

解题思想

这里使用map容器，差值作为键，重复次数作为值，因为map容器中的元素是按键升序排序的，因此，输出时需要逆序输出，这里给出了使用迭代器逆序输出map容器中元素的方法。

坑点提醒

题目要求输出的是有重复的差值及其重复次数，也就是输出的某个差值其重复次数一定是大于1的。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <map>

using namespace std;
map <int, int> mp;  //map容器中按键值自动升序排序
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        mp[tmp > i ? tmp - i : i - tmp]++;  //相应差值个数统计
    }
    map <int, int> :: iterator it = mp.end();   //it指向最后一个元素的下一个地址
    for (it--; it != mp.begin(); it--) {
        if (it -> second >1) {
            cout << it -> first << " " << it -> second << endl;
        }
    }
    if (it -> second > 1) {
        cout << it -> first << " " << it -> second << endl; //输出mp的第一个元素
    }
    return 0;
}

题目来源：PAT乙级1083
作者：CHEN, Yue
单位：浙江大学

稀罕作者