F. Double Knapsack - 题解
比赛与标签
比赛: Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) 标签: constructive algorithms, two pointers 难度: *3000
题目大意喵~
主人你好呀~！这道题是这样的喵：
我们有两个大小都为 n 的多重集（就是说可以有重复数字的集合啦）A 和 B，里面的数字都在 1 到 n 之间。
我们的任务呢，就是分别从 A 和 B 中找到一个非空的子集，让这两个子集的元素总和相等！是不是听起来像个有趣的寻宝游戏呢，喵？
如果能找到，就要开心地打印出这两个子集的大小和它们在原数组中的下标（注意是 1-based 的哦）。如果找不到的话...emmm，不过这道题保证一定有解的啦，所以不需要担心输出 -1 的情况~
举个栗子： A = {10, 10, ...} B = {10, 9, 8, ...} 我们可以从 A 中选出第 2 个元素（值为 10），从 B 中选出第 5、8、10 个元素（值分别为 6, 3, 1），它们的和都是 10 呐！
解题思路的奇妙旅程！
这道题看起来可能有点吓人，毕竟子集的数量可是指数级别的，一个一个去试肯定会超时的说！但是不要怕，让本猫娘带你发现其中的奥秘喵~
我们的目标是找到两个子集，A_sub 和 B_sub，使得 sum(A_sub) = sum(B_sub)。
直接找子集太难了，但我们可以把它转换成一个和前缀和有关的问题！这是一个非常常见的技巧哦。我们先只考虑连续子数组的情况，看看能不能找到线索。一个连续子数组 A[l...r] 的和可以表示为 sA[r] - sA[l-1]，其中 sA 是 A 的前缀和数组。
所以，我们的目标就变成了找到 sA[r_a] - sA[l_a-1] = sB[r_b] - sB[l_b-1]。 把这个等式稍微变一下形，就成了： sA[r_a] - sB[r_b] = sA[l_a-1] - sB[l_b-1]
哇！看到这个形式，主人有没有灵光一闪？我们只需要找到两对不同的下标 (i, j) 和 (p, q)，使得 sA[i] - sB[j] = sA[p] - sB[q] 就行啦！
但这还是有 n*n 种组合，太多了。我们需要一个更聪明的办法来锁定目标！
鸽巢原理的魔法！
这里就要请出我们强大的数学工具——鸽巢原理（Pigeonhole Principle）啦！
为了应用鸽巢原理，我们需要构造一些“鸽子”和一些“鸽巢”。
首先，为了方便讨论，我们不妨假设 A 的总和小于等于 B 的总和，也就是 sA[n] <= sB[n]。（如果不是这样，我们只要交换 A 和 B 的角色就好了，思路是完全一样的~）
现在，我们来定义我们的“鸽子”。我们考虑 n+1 个 A 的前缀和：sA[0], sA[1], ..., sA[n]（其中 sA[0] = 0）。 对于每一个 sA[i]，我们都在 B 的前缀和数组 sB 中，找到一个“搭档” sB[j]。这个搭档 sB[j] 是 sB 数组中第一个大于或等于 sA[i] 的值。我们可以用二分查找（lower_bound）或者双指针法来高效地找到它。
找到了搭档 (sA[i], sB[j])，我们来计算它们的差值 d_i = sB[j] - sA[i]。
现在我们来分析一下这个差值 d_i 的范围：
- 因为我们找的
sB[j]是大于等于sA[i]的，所以d_i >= 0。 - 因为
sB[j]是第一个满足条件的，所以它前一个前缀和sB[j-1]肯定小于sA[i]。 所以，d_i = sB[j] - sA[i] < sB[j] - sB[j-1] = B[j]。 - 题目告诉我们，B 中的每个元素都小于等于
n。所以B[j] <= n。 - 结合起来，我们就得到了
0 <= d_i < n。
也就是说，我们计算出的差值 d_i 只可能取 0, 1, ..., n-1 这 n 个整数值。这些就是我们的“鸽巢”！
我们有多少只“鸽子”呢？我们对 i = 0, 1, ..., n 都计算了一个差值，所以总共有 n+1 个差值，也就是 n+1 只鸽子！
把 n+1 只鸽子放进 n 个鸽巢里，根据鸽巢原理，必然至少有一个鸽巢里有两只或以上的鸽子！
这说明，我们一定能找到两个不同的 A 的前缀和下标 p 和 q（假设 p < q），它们对应的差值是相同的！ 设 sA[p] 的搭档是 sB[j_p]，sA[q] 的搭档是 sB[j_q]。 我们有： sB[j_p] - sA[p] = sB[j_q] - sA[q]
再次变形！ sA[q] - sA[p] = sB[j_q] - sB[j_p]
看呐！等式左边是 A 中从 p+1 到 q 的元素之和，右边是 B 中从 j_p+1 到 j_q 的元素之和！我们成功找到了两个和相等的非空子数组！
所以，算法步骤就是：
- 计算 A 和 B 的前缀和数组
sA和sB。 - 比较
sA[n]和sB[n]的大小，确定哪个数组扮演“A”的角色（总和较小那个），哪个扮演“B”的角色。 - 遍历
i从 0 到n，对于每个sA[i]，找到它在sB中的搭档sB[j]，计算差值d = sB[j] - sA[i]。 - 用一个数组
pos记录每个差值d第一次出现时i的值。 - 如果发现当前的差值
d之前已经出现过了（在i=p时），那么我们就找到了解！解就是 A 的p+1到i的部分，和 B 的j_p+1到j_i的部分。
这个方法保证能找到解，是不是很神奇喵~
代码实现喵~
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 使用C++标准库的快速IO，让程序跑得更快喵~
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
// 使用1-based索引，所以数组大小是n+1
vector<long long> A(n + 1), B(n + 1);
for (int i = 1; i <= n; i++) {
cin >> A[i];
}
for (int i = 1; i <= n; i++) {
cin >> B[i];
}
// 计算前缀和数组，sA[i] = A[1] + ... + A[i]
vector<long long> sA(n + 1, 0), sB(n + 1, 0);
for (int i = 1; i <= n; i++) {
sA[i] = sA[i - 1] + A[i];
sB[i] = sB[i - 1] + B[i];
}
// iA[i] 存储 sA[i] 在 sB 中的搭档的下标 j
// iB[i] 存储 sB[i] 在 sA 中的搭档的下标 j
// 这是为了处理 sA[n] > sB[n] 的情况
vector<int> iA(n + 1), iB(n + 1);
// 为了方便，我们先假设 sum(A) <= sum(B)
// 如果实际情况相反，也没关系，我们用一个 if-else 来处理
bool swap_roles = sA[n] > sB[n];
// 我们总是让总和较小的那个数组做“主数组”，去匹配总和较大的
if (!swap_roles) { // Case 1: sA[n] <= sB[n]
vector<int> pos(n + 1, -1); // pos[d] 记录差值为d时，主数组的下标
for (int i = 0; i <= n; i++) {
// 找到 sB 中第一个 >= sA[i] 的元素
auto it = lower_bound(sB.begin(), sB.end(), sA[i]);
int j = it - sB.begin();
// 计算差值
long long diff_val = sB[j] - sA[i];
int d = static_cast<int>(diff_val);
// 检查这个差值是否出现过
if (pos[d] != -1) {
// 找到了！之前在 p = pos[d] 处也得到了这个差值
int p = pos[d];
// 对应的 sB 中的下标
auto it_p = lower_bound(sB.begin(), sB.end(), sA[p]);
int j_p = it_p - sB.begin();
// 输出A的子集
cout << i - p << "\n";
for (int k = p + 1; k <= i; k++) {
cout << k << (k == i ? "" : " ");
}
cout << "\n";
// 输出B的子集
cout << j - j_p << "\n";
for (int k = j_p + 1; k <= j; k++) {
cout << k << (k == j ? "" : " ");
}
cout << "\n";
return 0; // 找到一组解就结束啦
}
// 记录这个差值第一次出现的位置
pos[d] = i;
}
} else { // Case 2: sA[n] > sB[n]，交换A和B的角色
vector<int> pos(n + 1, -1);
for (int i = 0; i <= n; i++) {
// 现在B是主数组，在sA中找搭档
auto it = lower_bound(sA.begin(), sA.end(), sB[i]);
int j = it - sA.begin();
long long diff_val = sA[j] - sB[i];
int d = static_cast<int>(diff_val);
if (pos[d] != -1) {
int p = pos[d];
auto it_p = lower_bound(sA.begin(), sA.end(), sB[p]);
int j_p = it_p - sA.begin();
// 输出A的子集
cout << j - j_p << "\n";
for (int k = j_p + 1; k <= j; k++) {
cout << k << (k == j ? "" : " ");
}
cout << "\n";
// 输出B的子集
cout << i - p << "\n";
for (int k = p + 1; k <= i; k++) {
cout << k << (k == i ? "" : " ");
}
cout << "\n";
return 0;
}
pos[d] = i;
}
}
return 0;
}（喵~ 上面的AC代码为了更清晰地展示逻辑，我稍微调整了结构并加了详细注释，但核心思想和原代码是一样的哦！原代码通过一个巧妙的 iA 和 iB 数组预处理，将两个分支合并，也是非常聪明的实现方式！这里为了教学目的，把两个情况分开写更容易理解~）
复杂度分析的说
- 时间复杂度: O(N log N) 的说。 计算前缀和是 O(N)。之后我们有一个循环，会执行 N+1 次。在循环内部，
lower_bound函数在大小为 N+1 的数组上进行二分查找，需要 O(log N) 的时间。所以总的时间复杂度就是 O(N log N) 啦。如果用双指针来代替lower_bound，可以优化到 O(N) 哦！ - 空间复杂度: O(N) 的说。 我们需要存储原始数组 A, B，前缀和数组
sA,sB，以及记录差值位置的pos数组。这些都需要 O(N) 的空间。
知识点与总结喵！
这道题真是一次美妙的思维探险，它完美地展示了如何将一个看似复杂的问题，通过巧妙的转化和经典的数学原理来解决！
鸽巢原理 (Pigeonhole Principle): 这是本题的灵魂！通过构造
n+1个范围在[0, n-1]内的差值，我们能够断定一定存在相等的差值，从而保证解的存在性。这种构造性的证明方法非常强大！前缀和 (Prefix Sums): 解决子数组/子集和问题的利器。它能将求和操作从 O(N) 降到 O(1)，是很多问题的基础。
构造性算法 (Constructive Algorithms): 我们的目标不仅仅是判断解是否存在，而是要构造出一个具体的解。本题的思路就是一个典型的构造性算法。
二分查找 / 双指针 (Binary Search / Two Pointers): 用于在有序序列中高效地查找“配对”元素。这里我们用它来寻找
sB[j] >= sA[i]的最小j。
希望这篇题解能帮助主人理解这道题的精妙之处！继续努力，你一定能成为超厉害的算法大师的，喵~！加油哦！