题意描述
Codeforces
链接
给你两个可重集 \(A, B\)，\(A, B\) 的元素个数都为 \(n\)，它们中每个元素的大小 \(x\in [1,n]\)。请你分别找出 \(A, B\)
的子集，使得它们中的元素之和相等。
数据范围：\(1 \leq n \leq 10^6\)
解题思路
我甚至菜到这是我做的第一道紫题
构造方法
本题显然需要构造。
首先我们维护 \(A\) 的前缀和 \(\text{sA}\)，\(B\) 的前缀和 \(\text{sB}\)。然后维护双指针指向两前缀和的第一个元素。这时我们将指向
\(\text{sA}\) 的指针不停加 \(1\)，同时指向 \(\text{sB}\)
的指针在满足下一个位置指的数小于等于 \(\text{sA}\)
的指针所指的数时不停向前移动，最后记录下 \(\text{sA}\) 的指针指向的值和 \(\text{sB}\)
指针指向的值的差及下标。若差已经存在，将存在的差的下标的前面的数删去后后面的差即可变为
\(0\)，故两差坐标之间的数即为答案。
正确性证明
接下来我们需要证明本题绝对有解，且所有解中至少有一种解所取的子集在原集合中是相邻的。
设指针下标为 \(p\)，\(q\)。该题始终满足 \(\text{sA}_p - \text{sB}_q <
n\)，若两差大于 \(n\)，则 \(q\)
必定可以后移，不为最优。因为集合中的所有数都小于等于 \(n\)。
所以我们目前有 \(sA_0 - sB_q, sA_1 - sB_q,
sA_3 - sB_q, \cdots, sA_n - sB_q\) 总共 \(n + 1\) 个差。但所有差只有 \(0, 1, 2, \cdots, n - 1\) 总共 \(n\)
种。根据鸽巢原理可知至少有一种差出现了不止一次。故用该方法本题保证有解。
代码演示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <cstdio>
#include <cstring>
#include <iostream>
const int MAXN = 1000000;
int main() {
int n;
static int a[MAXN + 1], b[MAXN + 1];
std::cin >> n;
static long long sa[MAXN + 1], sb[MAXN + 1];
sa[0] = sb[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sa[i] = sa[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
sb[i] = sb[i - 1] + b[i];
}
static bool vis[MAXN + 1];
static std::pair<int, int> pos[MAXN + 1];
memset(vis, false, sizeof(vis));
int p = 1, q = 0;
vis[0] = true;
bool find = false;
for (; p <= n; p++) {
while (q < n && sb[q + 1] <= sa[p]) q++;
if (vis[sa[p] - sb[q]]) {
find = true;
break;
} else {
vis[sa[p] - sb[q]] = true;
pos[sa[p] - sb[q]] = std::make_pair(p, q);
}
}
if (find) {
std::cout << p - pos[sa[p] - sb[q]].first << std::endl;
for (int i = pos[sa[p] - sb[q]].first + 1; i <= p; i++) printf("%d ", i);
std::cout << std::endl;
std::cout << q - pos[sa[p] - sb[q]].second << std::endl;
for (int i = pos[sa[p] - sb[q]].second + 1; i <= q; i++) printf("%d ", i);
std::cout << std::endl;
} else std::cout << "-1" << std::endl;
return 0;
}
|