题目大意

给定一个长度为 $N$ 的整数序列 $h_1, h_2, \dots, h_N$，要求将其划分为两个非空的子序列，使得每个子序列中的元素（按升序排列后）都构成一个等差数列。

如果存在多种划分方案，输出任意一种；如果不存在这样的划分，输出 -1。

解题思路

关键观察

1. 排序的必要性：由于要求子序列按升序排列后构成等差数列，首先需要对原序列进行排序，这样可以简化后续的构造过程。

2. 等差数列的性质：一个等差数列由首项和公差唯一确定。对于长度为 $k$ 的等差数列，只需要知道前两项（或任意两项）就能确定整个序列。

3. 划分策略：由于要划分成两个等差数列，其中一个等差数列的前几项很可能来自排序后序列的开头部分。我们可以尝试几种最有可能的初始情况。

算法框架

步骤1：排序预处理

将输入序列按升序排序，便于后续处理。

步骤2：尝试关键情况

基于观察，我们尝试三种最有可能成功的初始情况：

1. 情况1：第一个等差数列以 $a[1]$ 为首项，$a[2]-a[1]$ 为公差
2. 情况2：第一个等差数列以 $a[1]$ 为首项，$a[3]-a[1]$ 为公差
3. 情况3：第一个等差数列以 $a[2]$ 为首项，$a[3]-a[2]$ 为公差

步骤3：验证与调整

对于每种尝试的情况：

• 首先根据首项和公差构造第一个等差数列
• 剩余元素自动归入第二个序列
• 检查第二个序列是否构成等差数列
• 如果不满足，尝试通过移动元素来调整两个序列

步骤4：边界情况处理

• 当 $N = 2$ 时，任何划分都满足条件（单个元素视为公差为0的等差数列）
• 如果所有尝试都失败，输出 -1

实现细节

数据结构选择

• 多重集合：用于维护未分配的元素，支持快速查找和删除
• 哈希表：用于统计相邻元素的差值，判断是否构成等差数列
• 标记数组：记录每个元素属于哪个子序列

可行性检查

通过统计相邻元素的差值种类数来判断：

• 如果差值种类数 $\leq 1$，说明构成等差数列
• 否则需要继续调整

调整策略

当第二个序列不满足等差数列条件时：

• 从第一个序列中取出元素加入第二个序列
• 动态更新相邻元素的差值统计
• 检查是否满足条件

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自排序和多次线性扫描
• 空间复杂度：$O(N)$，用于存储各种辅助数据结构

样例分析

样例1

输入：4
      1 3 2 4
排序后：1 2 3 4
输出：第一个序列 [1, 2]，第二个序列 [3, 4]
      两个都是公差为1的等差数列

样例2

输入：6
      23 4 7 6 8 15
排序后：4 6 7 8 15 23
输出：第一个序列 [4, 6, 8]，第二个序列 [7, 15, 23]
      第一个公差为2，第二个公差为8

总结

本题的核心在于利用等差数列的性质，通过有限的尝试和调整来寻找可行的划分方案。关键在于识别出最有可能成功的几种初始情况，并通过有效的数据结构来验证和调整划分方案。

这种"尝试+验证+调整"的思路在解决构造类问题时非常实用，值得学习和掌握。