CF1413C Perform Easily

[lyccrius]

很妙的一道题。

将所有 $b - a$ 的值预处理并记录其来源 $b$。

排序。

双指针扫一遍，并对每个来源 $b$ 的 $i$ 计数。

当当前区间内所有 $b$ 的 $i$ 都出现一遍时更新答案。

时间复杂度 $\mathcal O(n)$

#include <iostream>
#include <algorithm>
#include <vector>

const int maxN = 1e5;
const int inf = 1e9;

int n;
int a[10];
int b[maxN + 10];
int c[maxN + 10];
int t;
int ans = inf;

struct Node {
    int i;
    int d;

    bool operator<(const Node &other) const {
        return d < other.d;
    }
};

typedef std::vector<Node>::iterator vit;

std::vector<Node> node;

void Add(Node node) {
    if (c[node.i] == 0) t++;
    c[node.i]++;
    return;
}

void Del(Node node) {
    c[node.i]--;
    if (c[node.i] == 0) t--;
    return;
}

int main() {
    for (int i = 1; i <= 6; i++) std::cin >> a[i];
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> b[i];
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= n; j++) {
            node.push_back((Node) {j, b[j] - a[i]});
        }
    }
    std::sort(node.begin(), node.end());
    vit l = node.begin();
    vit r = node.begin();
    while (r < node.end()) {
        while (t < n && r < node.end()) Add(*r), r++;
        while (t >= n) ans = std::min(ans, (r - 1)->d - l->d), Del(*l), l++;
    }
    std::cout << ans;
    return 0;
}