代数类。作为《挑战编程-程序设计竞赛训练手册》第二章第一题,入门级别。
Q10038: Jolly Jumpers
有n个整数的序列我们称为jolly jumper,如果相邻的2个数其差的绝对值恰好为1到n-1。例如:
1 4 2 3
就是jolly jumper(n=4)。因为相邻2数的差的绝对值为3,2,1,就是1到n-1。但是
1 4 2 -1 6
不是jolly jumper(n=5)。因为相邻2数的差的绝对值为3,2,3,7,并非1到n-1。
你的任务是写一个程式来判断一个整数序列是否为jolly jumper。
Input
每组测试资料一列,第一个正整数为 n(n < 3000),代表此整数序列的长度。接下来有n个整数,代表此整数序列。请参考Sample Input。
Output
对每一组测试资料,输出此整数序列是否为jolly jumper。请参考Sample Output。
Sample Input
4 1 4 2 3 5 1 4 2 -1 6
Sample Output
Jolly Not jolly
我的解法:
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> #include <vector> #include <iterator> #include <cmath> #include <algorithm> using namespace std; void print_coll(const vector<int>& coll) { copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " ")); cout << endl; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int n = 0; while (cin >> n) { vector<int> coll(n); vector<bool> digit(n - 1, false); for (int i = 0; i < n; ++i) { cin >> coll[i]; } /*print_coll(coll);*/ bool is_jolly = true; for (int i = 1; i < n; ++i) { int d = abs(coll[i] - coll[i - 1]) - 1; if (d < 0 || d >= n - 1) { is_jolly = false; break; } digit[d] = true; } if (is_jolly) { if (find(digit.begin(), digit.end(), false) != digit.end()) { is_jolly = false; } } if (is_jolly) { cout << "Jolly" << endl; } else { cout << "Not jolly" << endl; } } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////