JollyJumpers题目的问题Asequenceofn>0integersiscalledajollyjumperiftheabsolutevaluesofthedifferencebetweensuccessiveelementstakeonallthevalues1throughn-1.Forinstance,1423isajollyjumper,becausetheabsolutes

Question

Jolly Jumpers题目的问题
A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,
1 4 2 3
is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.
Input
Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.
Output
For each line of input, generate a line of output saying "Jolly" or "Not jolly".
Sample Input
4 1 4 2 3 这个为什么会是jolly呢，没有相差4的值啊
5 1 4 2 -1 6
Sample Output
Jolly
Not jolly

Answer 1

你理解错了。 Jelly Jumers的定义是说：给定一个包含n个元素的序列｛a｝，如果i =[1,n-1], 而且|a(i+1)-a(i)|能够覆盖所有的1~n-1，那么这个序列就是Jelly Jumers。

以序列: 1 4 2 3为例， 4-1 ＝3；2-4=-2-->2; 3-2=1; 这个序列有4个元素，而其差值序列恰恰涵盖了是1~n-1即1~3序列的所有元素，所以是Jolly Jumpers； 而1 4 2 -1 6则只产生了3 2 3 7而不是期待的1 2 3 4因此不是Jolly。

你没有指定具体语言，下面是C++的实现，可以很容易修改为C。 （只对输入作了简单的检查）

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

#define MAX_NUM 3000

using namespace std;


bool isJolly(const vector<int> &vi);

int main(int argc, char** argv) 
{       
    vector<int> vi;
    
    cout << "Input a sequence of int for Jolly Jumpers testing." << endl;
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(vi));
    
    if (vi[0] > MAX_NUM || vi[0] < 2)
    {
        cerr << "Out of the range." << endl;
        return -1;
    }
    
    if (vi.size() != vi[0]+1)
    {
        cerr << "Incomplete sequence." << endl;
        return -2;
    }
       
    if (isJolly(vi))
       cout << "Jolly" << endl;
    else
       cout << "Not jolly" << endl;
    
    return 0;
}

bool isJolly(const vector<int> &vi)
{
    int n = vi[0];
    size_t len = vi.size();
    vector<int>flag(n);
    
    for (int i = 1; i < len-1; i++)
    {
        int tmp = vi[i+1]-vi[i];
        tmp = (tmp>0)?tmp:(-tmp);
        if (tmp < flag.size())
          flag[tmp] = 1;
    }
    
    return (find(flag.begin()+1, flag.end(), 0) == flag.end());
}