简要题意
给定一个含有 个元素的可重集
，一个数 和一个含有 个数的可重集 ，现在要求 中每个数和
中任意一个数作差使得作差后得到的新的集合 中最大的数和最小的数的差最小。
策略分析
首先考虑暴力，每个数最后的值都有 种可能，所以总可能数有 种，显然不行。题目中 的大小为 ，所以我们期待一个 的做法。我们发现，所有数也只有
种可能，想要枚举答案不可能，但我们可以枚举结果。于是我们想到把 中每个元素都和 中所有元素作差，最后得到 个数放入一个新的数组 。因为我们要考虑最大和最小的差最小，所以我们需要使
数组中的值变得有序，于是我们对其进行排序。排序后为了查找的时候保证查找的区间内的数必须包含原来
中每个数的至少一种差（显然其每个数都有 种差），我们要在插入
前给每个数打好标记，标记它来自于哪个数。
预处理做完后，我们考虑如何查找答案。因为我们需要一个区间最大值，还需要一个区间最小值，所以我们想到了用双指针来进行查找。我们设左指针为
，右指针为 。 先走，一直走到与 间包含了的数包含了原来
中每个数的至少一个结果为止。现在开始移动左指针，每移动一次就 与
所指的两数之差更新答案。当两指针之间包含的数不能包含原来
中每个数的至少一个结果时，就回到第一步重新开始移动 ，循环一轮即可得到答案。
枚举复杂度为 ，排序复杂度为
，最后搜索的复杂度为
，所以整个算法的时间复杂度为
，于是我们做完了，下面是代码。
参考代码
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
53
54
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
namespace SHAWN {
const int N = 1e6 + 7, INF = 1e9;
struct node { int val, id; }cp[N];
int n, idx, ans = INF;
int a[7], b[N], cnt[N];
bool cmp(node x, node y) { return x.val < y.val; }
int work()
{
for (int i = 1; i <= 6; ++i) { cin >> a[i]; }
cin >> n;
if (n == 1) { cout << "0\n"; return 0; }
for (int i = 1; i <= n; ++i) {
cin >> b[i];
for (int j = 1; j <= 6; ++j) {
cp[++idx] = {b[i] - a[j], i};
}
cnt[i] = 0;
}
sort(cp + 1, cp + idx + 1, cmp);
int lidx = 1, ridx = 0, ncnt = 0;
while (ridx < idx) {
if (!cnt[cp[++ridx].id]) { ++ncnt; }
++cnt[cp[ridx].id];
while (lidx < ridx && cp[ridx].val - cp[lidx].val >= ans) {
if (cnt[cp[lidx].id] == 1) { --ncnt; }
--cnt[cp[lidx].id];
++lidx;
}
while (lidx < ridx && ncnt == n) {
ans = min(ans, cp[ridx].val - cp[lidx].val);
if (cnt[cp[lidx].id] == 1) { --ncnt; }
--cnt[cp[lidx].id];
++lidx;
}
}
cout << ans << '\n';
return 0;
}
}
signed int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
return SHAWN :: work();
}
|
