AcWing362. 区间

题目描述

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

解题思路

(qquad) 根据前缀和思想，我们用(s[k])表示最好选法中，整数集合(Z)包含了(0sim k)中的(s[k])个数，那在整数集合中(a_ile xle b_i)的数也就是(s[b_i]-s[a_i-1]ge c_i)，那我们就可以看出一个差分约束系统，将(a_i-1)向(b_i)连一条权重为(1)的有向边。

(qquad)但是如果要求解，那这一个差分约束的条件不够，应该再找几个：

(qquadqquadLarge a.)由于(0sim k)中间选的数不会(0sim k - 1)的少，所以(s[k] - s[k-1]ge 0)

(qquadqquadLarge b.)由于一个数至多只能选一次，所以(s[k]-s[k-1] le 1)，转化成(s[k-1]-s[k]ge -1)

整理上式我们可以得到一个差分约束系统

然后就是求一个(-1)到(50001)的最长路，为了方便可以把所有下标(+1)

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5e4 + 10, M = 3 * N;
int dist[M], st[M], q[M], hh = 0, tt = 1;
int h[M], e[M], ne[M], w[M], idx;
int n, a, b, c;

int spfa() 
{
    memset(dist, 0xcf, sizeof dist);
    
    q[0] = dist[0] = 0, st[0] = true;
    
    while (hh != tt) 
    {
        int t = q[hh ++ ];
        st[t] = 0;
        if (hh == N) hh = 0;
        
        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]) 
                {
                    q[tt ++ ] = j, st[j] = 1;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    
    return dist[50001];
}

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

int main() 
{
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    for (int i = 1; i <= 50001; i ++ ) 
        add(i - 1, i, 0), add(i, i - 1, -1);
        
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b + 1, c);
    }
    
    printf("%d
", spfa());
    
    return 0;
}