10038 Jolly Jumpers

題目連結

題目敘述

長度為 n > 0 的整數序列稱為 jolly jumper，如果該序列相鄰元素之間絕對差值包含了從 1 到 n−1 的所有整數

例如序列

1 4 2 3

是 jolly jumper，因為相鄰元素的絕對差分別為 3、2 和 1，恰好包含了 1 到 3 的所有整數

定義中也隱含，任何單一整數的序列都是 jolly jumper

請撰寫程式判斷輸入的多組序列是否為 jolly jumper

輸入說明

每行輸入包含一個整數 n（n ≤ 3000），接著是 n 個整數，代表該序列的元素

輸出說明

對每組輸入的序列，輸出一行：

• 若該序列為 jolly jumper，輸出 Jolly
• 否則輸出 Not jolly

解題思路

建立一個大小為 n 的計數陣列 cnt（初始為 0），用來紀錄差值出現的次數
遍歷序列中相鄰的元素對 (vc[i-1], vc[i])，計算差的絕對值 k = abs(vc[i] - vc[i-1])
若 k 在範圍 [1, n-1] 內，將 cnt[k] 加 1，表示這個差值出現過
遍歷 cnt，檢查從 1 到 n−1 是否都有出現（即 cnt[i] != 0）

• 如果有任何一個值沒出現，代表該序列不是 jolly jumper
• 否則，該序列是 jolly jumper

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        vector<int> vc(n),cnt(n);
        for(int i=0;i<n;i++)cin>>vc[i];
        for(int i=1;i<n;i++){
            int k = abs(vc[i]-vc[i-1]);
            if(1<=k && k<n)cnt[k]++;
        }
        bool flag = false;
        for(int i=1;i<n;i++){
            if(cnt[i]==0){
                cout<<"Not jolly"<<endl;
                flag = true;
                break;
            }
        }
        if(!flag)cout<<"Jolly"<<endl;
    }
    return 0;
}