[蓝桥杯 2017 国 A] 区间移位

GitHub跳转原题关系图返回列表

二分最大位移后，把每个区间转成带最早可接点和最晚失效点的任务，按失效点最小优先贪心推进覆盖前缀。

OJ: luogu

题目 ID: P8660

难度:提高+/省选-

标签:二分答案贪心优先队列区间建模

日期: 2026-06-20 21:34

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给出 n 个区间 [a_i,b_i]。

现在可以把每个区间整体平移成 [a_i+c_i,b_i+c_i]，要求所有平移后的区间并起来以后，完整覆盖 [0,10000]。

我们要让

max |c_i|

尽量小，并输出这个最小值。

思路

先看一个最容易理解的小数据暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 18;
const int TARGET = 20000; // 坐标统一乘 2。

int n;
int a[MAXN], b[MAXN];

struct Interval {
    int need_left;
    int dead;
    int len;
};

Interval seg[MAXN];
unordered_map<long long, int> memo;

long long encode_state(int mask, int covered) {
    return (static_cast<long long>(mask) << 20) | covered;
}

// 小数据暴力：枚举当前还能接上的所有区间，求最远能覆盖到哪里。
int dfs(int mask, int covered) {
    long long key = encode_state(mask, covered);
    unordered_map<long long, int>::iterator it = memo.find(key);
    if (it != memo.end()) {
        return it->second;
    }

    int best = covered;

    for (int i = 0; i < n; i++) {
        if ((mask >> i) & 1) {
            continue;
        }
        if (seg[i].need_left > covered) {
            continue;
        }
        if (seg[i].dead <= covered) {
            continue;
        }

        int next_covered = min(covered + seg[i].len, seg[i].dead);
        int value = dfs(mask | (1 << i), next_covered);
        if (value > best) {
            best = value;
        }
    }

    memo[key] = best;
    return best;
}

bool check(int lim2) {
    for (int i = 0; i < n; i++) {
        seg[i].need_left = a[i] - lim2;
        seg[i].dead = b[i] + lim2;
        seg[i].len = b[i] - a[i];
    }

    memo.clear();
    return dfs(0, 0) >= TARGET;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        a[i] *= 2;
        b[i] *= 2;
    }

    int left = 0;
    int right = TARGET;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if ((left & 1) == 0) {
        cout << left / 2 << '\n';
    } else {
        cout << left / 2 << ".5\n";
    }

    return 0;
}

brute.cpp 固定一个答案 K 以后，直接 DFS 枚举“下一个使用哪个区间”，求最远能把覆盖前缀推进到哪里。

这个版本很适合理解题意，但正式数据里 n 最大有 10000，显然不能这样枚举。

关键是先把固定 K 的判定模型看清楚。

设当前已经连续覆盖到了 [0,p]。 如果第 i 个区间最多只能平移 K，那么它能接上当前前缀，当且仅当：

  • a_i-K <= p
  • p < b_i+K

一旦接上，它最多只能把前缀推进到：

min(p + (b_i-a_i), b_i+K)

注意这里不是直接把区间当成 [a_i-K,b_i+K] 去做普通并集覆盖，因为区间长度不能变，它只是整体平移。

于是固定 K 后，每个区间都可以抽象成一个三元组：

  • need_left = a_i-K
  • dead = b_i+K
  • len = b_i-a_i

含义是：

  • 当前前缀至少到 need_left，这个区间才可用
  • 当前前缀一旦达到 dead，这个区间就彻底失效
  • 使用它以后，前缀最多增加 len

接下来问题就变成：

当前前缀从 0 开始，反复选择一个“已经可用且还没失效”的区间，让前缀尽量推进到 10000。

这里正确的贪心是：

每一步都优先使用当前失效点 dead 最小的区间。

原因很直观：

  • 失效点更小的区间更“着急”
  • 如果现在不用它，前缀继续往右走，它只会更容易彻底失效
  • 失效点更大的区间相对更能等待

实现时：

  1. 把所有区间按 need_left 从小到大排序
  2. 用小根堆维护当前已经可用的区间
  3. 堆关键字取 dead
  4. 每次先把 need_left <= covered 的区间加入堆
  5. 再把 dead <= covered 的失效区间弹掉
  6. 取堆顶区间，把 covered 更新为 min(covered + len, dead)

如果最终 covered >= 10000，说明这个 K 可行。

由于输入都是整数，而答案只会是整数或 0.5，所以把所有坐标统一乘 2 后，就可以完全用整数二分，不需要处理浮点误差。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int TARGET = 20000; // 把所有坐标乘 2，这样 0.5 也能变成整数处理。

int n;
int a[MAXN], b[MAXN];

struct Interval {
    int need_left; // 当前覆盖前缀至少要到这里，区间才能接上。
    int dead;      // 当前覆盖前缀一旦达到这里或更右，这个区间就接不上了。
    int len;       // 区间本身的长度。
};

Interval seg[MAXN];

bool cmp_interval(const Interval &x, const Interval &y) {
    if (x.need_left != y.need_left) {
        return x.need_left < y.need_left;
    }
    if (x.dead != y.dead) {
        return x.dead < y.dead;
    }
    return x.len < y.len;
}

// 检查当最大位移不超过 lim2/2 时，是否能覆盖整个 [0, 10000]。
bool check(int lim2) {
    for (int i = 1; i <= n; i++) {
        seg[i].need_left = a[i] - lim2;
        seg[i].dead = b[i] + lim2;
        seg[i].len = b[i] - a[i];
    }

    sort(seg + 1, seg + n + 1, cmp_interval);

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

    int covered = 0; // 当前已经连续覆盖到了 [0, covered]。
    int idx = 1;

    while (covered < TARGET) {
        while (idx <= n && seg[idx].need_left <= covered) {
            pq.push(make_pair(seg[idx].dead, seg[idx].len));
            idx++;
        }

        // 已经过期的区间，不可能再接住当前前缀，直接丢掉。
        while (!pq.empty() && pq.top().first <= covered) {
            pq.pop();
        }

        if (pq.empty()) {
            return false;
        }

        int dead = pq.top().first;
        int len = pq.top().second;
        pq.pop();

        covered = min(covered + len, dead);
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        a[i] *= 2;
        b[i] *= 2;
    }

    int left = 0;
    int right = TARGET;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if ((left & 1) == 0) {
        cout << left / 2 << '\n';
    } else {
        cout << left / 2 << ".5\n";
    }

    return 0;
}

复杂度

设 check(K) 的一次判定中：

  • 排序复杂度是 O(nlogn)O(n log n)
  • 每个区间最多入堆、出堆一次，总堆操作也是 O(nlogn)O(n log n)

所以一次判定是 O(nlogn)O(n log n)。

二分答案的范围是乘 2 后的 [0,20000]，因此总复杂度为：

O(nlognlogV)O(n log n log V)

其中 V = 20000。

空间复杂度是 O(n)O(n)。

总结

这题最容易走偏的地方，是把区间错误地当成 [a_i-K,b_i+K] 的普通扩张区间。

真正关键的是：

  • 区间只能平移，长度不变
  • 固定 K 后，每个区间本质上是一个“有最早可接点、最晚失效点、固定推进长度”的任务
  • 判定时按最早失效优先，用堆贪心推进前缀

把这个模型想清楚以后，整题就是一个标准的“二分答案 + 贪心判定”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析