AcWing362. 区间

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

AcWing362. 区间

2023-01-01 11:11:35 来源：博客园

(相关资料图)

题目描述

给定 \(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\)包含了\(0\sim k\)中的\(s[k]\)个数，那在整数集合中\(a_i\le x\le b_i\)的数也就是\(s[b_i]-s[a_i-1]\ge c_i\)，那我们就可以看出一个差分约束系统，将\(a_i-1\)向\(b_i\)连一条权重为\(1\)的有向边。

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

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

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

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

\[\left \{\begin{array}cs[b_i]-s[a_i-1]\ge c_i\\s[k] - s[k-1]\ge 0\\s[k-1]-s[k]\ge -1\end{array}\right.\]

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

代码

#include #include 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\n", spfa());        return 0;}

关键词：约束系统