洛谷 P1152 题解

传送门：P1152 欢乐的跳

更佳的阅读体验：洛谷 P1152 题解

简要题意：给定一个长度为 $n$ 的整数序列，判断所有相邻元素之间差的绝对值是否恰好包含了从 $1$ 到 $n - 1$ 的所有整数。

我们可以先新建一个辅助数组 $d$，计算出所有相邻元素之间的差。

接下来我们对 $d$ 从小到大排序。如果数组满足“欢乐的跳”，那么对于 $[1, n - 1]$ 中的每一个数 $i$，排序后一定有 $d_i = i$。逐个判断即可。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1010;
int n, a[N], d[N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) d[i] = abs(a[i] - a[i + 1]);
    sort(d + 1, d + n);
    for (int i = 1; i < n; ++i) if (d[i] != i) {
        cout << "Not jolly\n";
        return 0;
    } cout << "Jolly\n";
    return 0;
}