区间

差分约束 T4 362. 区间 - AcWing题库

给定 $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$ 最少包含多少个数。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$。

输出格式

输出一个整数表示结果。

数据范围

$1\le n\le 50000$,
$0\le a_i,b_i\le 50000$,
$0\le c_i\le b_i-a_i+1$

输入样例：

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例：

6

思路

题意是求满足 $a_i\le x\le b_i$ 个数不少于 $c_i$ 的集合 $Z$ 最少包含多少个元素。涉及区间, 不等式, 计数方面的问题。

既然是区间, 可以想到类似于数位DP的处理方式, 定义 $S_i$ 为 $[1,i]$ 中包含多少个元素, 那么范围在 $[a_i,b_i]$ 所包含的元素就为 $S_{b_i}-S_{a_i-1}$ 。

而每个 $S_i$ 具体的值又需要满足一系列不等式条件。这里就到了差分约束的回合。首先需要尽可能找全限制条件：

1. $S_i\ge S_{i-1}$ 。根据定义可得
2. $S_i-S_{i-1}\le 1$, 剩下一个元素时要么选要么不选, 故最多为1
3. $S_{b_i}-S_{a_i-1}\ge c_i$, 题目条件

既然是求最小值, 那么就是求下界中的最大值, 将不等式转化一下得：

1. $S_i\ge S_{i-1}+0$
2. $S_{i-1}\ge S_i-1$
3. $S_{b_i}\ge S_{a_i-1}+c_i$

而源点就是$S_0=0$ 。求一边SPFA单源最短路即可得到答案。因为题目中保证 $c_i$ 不超过区间长度, 故一定有界, 不需要判断正环。

最终结果就是$S_{50001}$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 5e4 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int q[N];
int dist[N];
bool st[N];
int 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);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0]= 0;
    st[0] = true;
    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;
        
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i <= 50001; i++)
    {
        add(i-1,i,0);
        add(i,i-1,-1);
    }
    for(int i = 0; i < n; i++)
    {
        int a, b , c;
        cin >> a >> b >> c;
        a++,b++;
        add(a-1, b, c);
    }
    
    spfa();
    
    cout << dist[50001] << endl;
    
    return 0;
}