P1152 欢乐的跳

题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

4 1 4 2 3

样例输出 #1

Jolly

样例 #2

样例输入 #2

5 1 4 2 -1 6

样例输出 #2

Not jolly

提示

$1\le n\le 1000$

1.题目分析

输入一行整数，第一个整数代表元素个数，后面的数代表各个元素。
计算这些元素相邻之间的差值，将差值排序，判断是否为公差为1的等差数列。

值得一提的是，采用任何一种排序都是可以的，这里采用的是最简单的选择排序。

2.题目思路

输入元素个数，将元素存入数组，
计算相邻两个数的差值，存入另外一个数组，
使用选择排序，将差值进行排序。

定义一个标记标量，遍历排序后的差值数组，
如果存在不连续的数（即公差不为1），修改标记变量。

最后，根据标记变量输出相应的结果即可。

3.代码实现

#include <iostream>

using namespace std;

int main() {
    int n;
    //输入元素的个数
    cin >> n;
    //定义存放整数的数组
    long long arr[n];
    //键入
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    long long temp;
    //存放相邻元素的差值
    long long dif[n - 1];
    for (int i = 0; i < n - 1; ++i) {
        dif[i] = abs(arr[i] - arr[i + 1]);
    }
    //将差值进行排序
    //这里使用的是选择排序
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            //大的往后排
            if (dif[i] > dif[j]) {
                temp = dif[i];
                dif[i] = dif[j];
                dif[j] = temp;
            }
        }
    }
    //判断差值绝对值是否为连续
    int flag = 1;
    for (int i = 0; i < n - 2; ++i) {
        //排序后，如果存在不连续的数，修改标记
        if (abs(dif[i] - dif[i + 1]) != 1) {
            flag = 0;
        }
    }
    //根据标记标量输出
    if (flag == 1) {
        cout << "Jolly";
    } else {
        cout << "Not jolly";
    }

    return 0;
}