题解 CF1413C Perform Easily

简要题意

给定一个含有 $6$ 个元素的可重集 $a$，一个数 $n$ 和一个含有 $n$ 个数的可重集 $b$，现在要求 $b$ 中每个数和 $a$ 中任意一个数作差使得作差后得到的新的集合 $b$ 中最大的数和最小的数的差最小。

策略分析

首先考虑暴力，每个数最后的值都有 $6$ 种可能，所以总可能数有 $6^n$ 种，显然不行。题目中 $n$ 的大小为 $10^5$，所以我们期待一个 $O(n\log n)$ 的做法。我们发现，所有数也只有 $6$ 种可能，想要枚举答案不可能，但我们可以枚举结果。于是我们想到把 $b$ 中每个元素都和 $a$ 中所有元素作差，最后得到 $6n$ 个数放入一个新的数组 $cp$。因为我们要考虑最大和最小的差最小，所以我们需要使 $cp$ 数组中的值变得有序，于是我们对其进行排序。排序后为了查找的时候保证查找的区间内的数必须包含原来 $b$ 中每个数的至少一种差（显然其每个数都有 $6$ 种差），我们要在插入 $cp$ 前给每个数打好标记，标记它来自于哪个数。

预处理做完后，我们考虑如何查找答案。因为我们需要一个区间最大值，还需要一个区间最小值，所以我们想到了用双指针来进行查找。我们设左指针为 $lidx$，右指针为 $ridx$。$ridx$ 先走，一直走到与 $lidx$ 间包含了的数包含了原来 $b$ 中每个数的至少一个结果为止。现在开始移动左指针，每移动一次就 $ridx$ 与 $lidx$ 所指的两数之差更新答案。当两指针之间包含的数不能包含原来 $b$ 中每个数的至少一个结果时，就回到第一步重新开始移动 $ridx$，循环一轮即可得到答案。

枚举复杂度为 $O(n)$，排序复杂度为 $O(n\log n)$，最后搜索的复杂度为 $O(n)$，所以整个算法的时间复杂度为 $O(n\log n)$，于是我们做完了，下面是代码。

参考代码

#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;
        // cnt数组和ncnt用来维护当前区间包含原来b数组中的数的结果的个数
        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();
}