区间

原题链接

题目描述

给定 \(n\) 个区间 \([a_i,b_i]\) 和 \(n\) 个整数 \(c_i\)。

你需要构造一个整数集合 \(Z\)，使得 \(\forall i\in[1,n]\)，Z 中满足 \(a_i\le x\le b_i\) 的整数 \(x\) 不少于 \(c_i\) 个。

求这样的整数集合 \(Z\) 最少包含多少个数。

---

差分约束

本题要求最小值，我们使用最长路来求解。

我们用 \(s[i]\) 来代表从 \(1\sim i\) 中被选出的数的个数。

因此可以得到以下的约束条件：

• \(s[i]\ge s[i-1]\Rightarrow s[i]\ge s[i-1]\)
• \(s[i]-s[i-1]\le 1\Rightarrow s[i-1]\ge s[i]-1\)
• \(s[b_i]-s[a_i-1]\ge c_i\Rightarrow s[b_i]\ge s[a_i-1]+c_i\)

由于 \(a_i,b_i\) 可能取到 \(0\)，将所有的数加 \(1\)，就相当于都没有加 \(1\)，不会影响答案。

由于加了 \(1\)，所以最终答案为 \(dist[50001]\)。

代码

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

const int N = 50010, M = 3 * N;

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa() {
    memset(dist, -0x3f, sizeof dist);

    queue<int> q;
    q.push(0);
    dist[0] = 0;

    while (q.size()) {
        int u = q.front();
        q.pop();

        st[u] = false;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a++;
        b++;
        add(a - 1, b, c);
    }

    for (int i = 1; i <= 50001; i++) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }

    spfa();

    cout << dist[50001] << endl;

    return 0;
}