题解：区间问题
一、题目背景
给定 (n) 个区间 ([a_i, b_i]) 和对应的 (n) 个整数 (c_i)，要求构造一个整数集合 (Z)，使得对于每个 (i\in[1,n])，集合 (Z) 中满足 (a_i\leq x\leq b_i) 的整数 (x) 的个数不少于 (c_i) 个，求这样的整数集合 (Z) 最少包含多少个数。
二、解题思路
本题可通过差分约束系统来解决，将问题转化为图论中的最短路径问题。把每个整数看作图中的节点，根据区间条件和整数之间的关系构建有向边，利用SPFA算法求解从源点到特定节点的最短距离，该最短距离即为整数集合 (Z) 的最少元素个数。
具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、距离数组（记录从源点到每个节点的最少整数个数）、队列数组以及节点是否在队列中的标记数组。
2. 编写添加边的函数，用于构建邻接表。
3. 实现SPFA算法，通过不断更新节点距离，最终得到从源点到各节点的最短距离。
4. 在 main 函数中：
- 读取区间的数量 (n)。
- 初始化邻接表，构建相邻整数节点之间的边（表示数量关系），即从 (i - 1) 到 (i) 的边权为 (0)（表示 (i) 处的整数个数可以不比 (i - 1) 处多），从 (i) 到 (i - 1) 的边权为 (-1)（表示 (i - 1) 处的整数个数最多比 (i) 处少 (1)）。
- 根据输入的区间和对应的 (c_i)，构建区间相关的边，将区间左端点减 (1) 到右端点的边权设为 (c_i)（表示该区间内至少有 (c_i) 个整数在集合 (Z) 中）。
- 调用SPFA算法计算最短距离。
- 输出从源点（这里可看作 (0) 节点）到 (50001) 节点的最短距离，即整数集合 (Z) 最少包含的元素个数。
三、代码逐段分析
（一）头文件和全局变量
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
// 注意这里视频中的写法是 M = 150010，数组会越界，可以改成M = N * 3 + 10。
const int N = 50010, M = N * 3 + 10;
int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N];
bool st[N];
- 头文件：
#include <cstdio>：用于标准输入输出函数，如scanf和printf。#include <cstring>：用于字符串操作和内存初始化函数，如memset。#include <iostream>：提供C++风格的输入输出流，如cin和cout。#include <algorithm>：包含一些常用的算法函数。using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
- 常量定义：
const int N = 50010, M = N * 3 + 10;：定义节点的最大数量（对应整数的范围）和边的最大数量。
- 变量定义：
int n;：表示区间的数量。int h[N], e[M], w[M], ne[M], idx;：邻接表相关数组，h[N]存储每个节点的头指针，e[M]存储边的终点，w[M]存储边权，ne[M]存储下一条边的指针，idx用于边的编号。int dist[N];：记录从源点到每个节点的距离，即满足条件的最少整数个数。int q[N];：队列数组，用于SPFA算法。bool st[N];：标记每个节点是否在队列中。
（二）添加边函数
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点，c 为边权。通过更新邻接表数组，将边的信息存储起来。
（三）SPFA算法函数
void spfa()
{
memset(dist, -0x3f, sizeof dist);
dist[0] = 0;
st[0] = true;
int hh = 0, tt = 1;
q[0] = 0;
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])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
- 初始化：
memset(dist, -0x3f, sizeof dist);：将距离数组初始化为一个极小值，表示未确定从源点到各节点的最少整数个数。dist[0] = 0;：源点（这里为 (0) 节点）到自身的距离为 (0)。st[0] = true;：标记源点在队列中。int hh = 0, tt = 1;和q[0] = 0;：初始化队列的头指针、尾指针，并将源点入队。
- 队列处理：
- 当队列不为空时，取出队头节点
t，标记为不在队列中。 - 遍历节点
t的所有邻接边，如果通过节点t到邻接节点j的距离更短，则更新距离dist[j]。 - 如果邻接节点
j不在队列中，则将其入队并标记为在队列中。
- 当队列不为空时，取出队头节点
- 结束条件：
- 当队列为空时，说明已经更新完所有可达节点的距离，函数结束。
（四）main 函数
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i < N; i ++ )
{
add(i - 1, i, 0);
add(i, i - 1, -1);
}
for (int i = 0; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a ++, b ++ ;
add(a - 1, b, c);
}
spfa();
printf("%d\n", dist[50001]);
return 0;
}
- 读取数据并初始化：
scanf("%d", &n);：读取区间的数量n。memset(h, -1, sizeof h);：初始化邻接表头指针数组为 (-1)。- 通过循环构建相邻整数节点之间的边，从 (i - 1) 到 (i) 的边权为 (0)，从 (i) 到 (i - 1) 的边权为 (-1)。
- 构建区间相关边：
- 通过循环读取每个区间的左端点
a、右端点b和对应的整数c，将区间左端点加 (1)（为了避免 (0) 节点的特殊处理），构建从a - 1到b的边，边权为c。
- 通过循环读取每个区间的左端点
- 计算最短距离并输出结果：
- 调用SPFA算法计算从源点到各节点的最短距离。
printf("%d\n", dist[50001]);：输出从源点到 (50001) 节点的最短距离，即整数集合 (Z) 最少包含的元素个数。
- 结束程序：
return 0;：程序正常结束。
四、时间复杂度和空间复杂度分析
（一）时间复杂度
- 输入和建图：读取 (n) 个区间并构建邻接表，时间复杂度为 (O(n))。
- SPFA算法：在最坏情况下，每个节点都可能入队 (N) 次，每次入队处理其邻接边，时间复杂度为 (O(Nm))，其中 (m) 是边的数量。但在实际情况中，SPFA算法通常比这个复杂度要快。这里边的数量 (m) 约为 (3N)（相邻节点边和区间边），所以实际时间复杂度约为 (O(N^2))。
总体时间复杂度为 (O(N^2 + n))，主要由SPFA算法的时间复杂度决定。
（二）空间复杂度
- 邻接表：存储边的信息，空间复杂度为 (O(m))，这里 (m) 约为 (3N)，所以为 (O(N))。
- 其他数组：距离数组
dist[N]、队列数组q[N]和标记数组st[N]，空间复杂度均为 (O(N))。
总体空间复杂度为 (O(N))。
希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。
