1 条题解
-
0
解题思路:
本题要求判断一个序列是否存在“有趣的跳跃”,即相邻元素的差值的绝对值排序后恰好构成到的连续序列。解决此问题的关键在于验证差值是否满足特定条件。
关键步骤:
计算相邻差值:遍历序列,计算每两个相邻元素的绝对差值。
记录差值唯一性:使用数组标记已出现的差值,若发现重复差值,立即判定不满足条件。
验证覆盖范围:检查所有到的整数是否均被差值覆盖,确保连续。实现细节:
数组标记:用数组记录差值的出现情况,索引对应差值,值为表示存在。
重复判断:在计算差值时,若发现重复值,直接标记为不满足条件。
范围检查:遍历到,若存在未被标记的数值,则判定不满足条件。特殊情况处理:
- 当序列长度为时,直接满足条件。
- 差值超出到范围或包含时,自动判定为不满足条件。
C++实现:
#include <cstdio> #include <cstring> #include <cmath> int subs[3100]; // 标记数组,记录差值的出现情况 int num[3100]; // 存储输入序列 int main() { int n; while (scanf("%d", &n) != EOF) { memset(subs, 0, sizeof(subs)); // 初始化标记数组 int flag = 1; // 初始标记为满足条件 for (int i = 0; i < n; i++) { scanf("%d", &num[i]); // 读入序列元素 if (i > 0) { int diff = abs(num[i] - num[i-1]); // 计算相邻差值绝对值 if (diff >= 1 && diff < n) { // 差值需在有效范围内 if (subs[diff] == 0) { subs[diff] = 1; // 标记该差值已出现 } else { flag = 0; // 重复差值,不满足条件 } } else { flag = 0; // 差值超出范围,不满足条件 } } } // 检查1到n-1是否全部被覆盖 if (n > 1) { for (int i = 1; i <= n-1; i++) { if (subs[i] != 1) { flag = 0; break; } } } printf(flag ? "Jolly\n" : "Not jolly\n"); } return 0; }
- 1
信息
- ID
- 1576
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 9
- 已通过
- 1
- 上传者