洛谷-P1152

这道题挺简单的，那我们开始吧！

题解仅供参考，如果有任何问题可以和我反馈，交流

题干

题目描述

一个 $n$ 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 $[1,n-1]$ 之间的所有整数，则称之符合“欢乐的跳”，如数组 ${1,4,2,3}$ 符合“欢乐的跳”，因为差的绝对值分别为：$3,2,1$。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数 $n(1 \le n \le 1000)$ 开始，接下来 $n$ 个空格隔开的在 $[-10^8,10^8]$ 之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

样例 #1

样例输入 #1

1
4 1 4 2 3

样例输出 #1

1
Jolly

样例 #2

样例输入 #2

1
5 1 4 2 -1 6

样例输出 #2

1
Not jolly

提示

$1 \le n \le 1000$

解析

简单看来，就是看一个数组相邻两个数字差是不是包括 $1、2、3···n$

思路

看一下范围，初步确定思路就是计算一下相邻两个的差值，利用桶存起来（出现这个数字，把对应下标设为1）

补充一下：

如果有一个差值为 $k$ ,那我们就让 $map[k] = 1$, 这样只需遍历1-n，看看有没有没出现过的差即可

代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;

int a[1005]; //输入的数组
int n; //个数
bool map[20000005]; //桶，-10^8,10^8 的整数，差值最大20^8

int main()
{
    cin >> n; //输入n
    for (int i = 1; i <= n; i++){
        cin >> a[i]; //循环输入数组
    }
    for (int i = 1; i < n; i++){
        map[abs(a[i+1] - a[i])] = 1; //计算差值(abs是取绝对值)，将对应的桶设为1
    }
    for (int i = 1; i < n; i++){ //检查1-n范围内有没有漏网之鱼
        if(map[i] == 0){
            cout << "Not jolly"; //若有，输出
            return 0;//结束
        }
    }
    cout << "Jolly"; //若没有，输出
    return 0;//结束
}

结束！