信息学奥赛一本通 1509：【例 1】Intervals | OpenJudge 百练 1201:Intervals
【题目链接】
ybt 1509：【例 1】Intervals
OpenJudge 百练 1201:Intervals
【题目考点】
1. 贪心算法 树状数组 并查集
2. 差分约束算法
【解题思路】
解法1：贪心算法+树状数组、并查集优化
该题属于区间选点问题，ybt 1324：【例6.6】整数区间 是给定一些区间，选择一些点使得每个区间范围内至少有1个点。
本题为：给定一些区间，选择一些点使得每个区间范围内至少有给定数量的点。
贪心选择：对每个区间，如果还需要选点，则尽量从区间右侧选点。
所有区间按照右端点 b b b从小到大排序，排序后第i区间范围为 [ a i , b i ] [a_i, b_i] [ai,bi]，其中需要至少选择 c i c_i ci个点。
贪心选择的具体解释：
- 如果该区间中已经选择点的数量大于等于 c i c_i ci，则不需要再选点。
- 如果该区间中已经选择点的数量小于 c i c_i ci，则从 b i b_i bi到 a i a_i ai从大到小遍历每个点，遇到未选择的点就选择该点，直到选够 c i c_i ci个点。
贪心选择性质的证明：
- 证明存在最优解包含第一次的贪心选择
第一次的贪心选择为：在 [ a 1 , b 1 ] [a_1,b_1] [a1,b1]中选择区间 [ b 1 − c 1 + 1 , b 1 ] [b_1-c_1+1, b_1] [b1−c1+1,b1]中的整数点，共 c 1 c_1 c1个点。
反证法：假设所有最优解都不包含第一次的贪心选择
也就是说在 [ a 1 , b 1 − c 1 ] [a_1, b_1-c_1] [a1,b1−c1]选择了一些点，而 [ b 1 − c 1 + 1 , b 1 ] [b_1-c_1+1, b_1] [b1−c1+1,b1]中存在未被选择的点。设在 [ a 1 , b 1 − c 1 ] [a_1, b_1-c_1] [a1,b1−c1]中选择了点 G G G，而 [ b 1 − c 1 + 1 , b 1 ] [b_1-c_1+1, b_1] [b1−c1+1,b1]中点 F F F未被选择。
现在不选择点 G G G转而选择点 F F F，第2、第3等后面的区间中已选择的点可能会增加，也可能不变。每个区间的选点数量都满足要求，总选点数量不变。因此这样变换选择点后，此时的选点方案仍然是最优解。
将在 [ a 1 , b 1 − c 1 ] [a_1, b_1-c_1] [a1,b1−c1]中选择的所有点都去掉，转而在 [ b 1 − c 1 + 1 , b 1 ] [b_1-c_1+1, b_1] [b1−c1+1,b1]中选择相同数量的点，最后选择的点就是 [ b 1 − c 1 + 1 , b 1 ] [b_1-c_1+1, b_1] [b1−c1+1,b1]中的每个点，这也就是进行了贪心选择，这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖，原命题得证。- 假设最优解包含前k次的贪心选择，证明存在最优解包含第k+1次的贪心选择：
证明过程与第1点的证明过程相似，不再赘述。
具体实现：
设vis数组，vis[i]表示第i点是否已被选择。
对于每个区间，先遍历整个区间，统计出已选点数量，也就是求出待选择点的数量。
- 如果待选择点的数量为0，就看下一个区间。
- 否则，从区间右端点开始，向前遍历，遇到未选择的点，就选择一个点，直到待选择点的数量为0。统计选点总数量，就是问题结果。
该算法的复杂度达到了 O ( n 2 ) O(n^2) O(n2)，尽管可以通过ybt 1509与OpenJudge 百练 1201的测试点，但在LOJ10087. 「一本通 3.4 例 1」Intervals，以及MYOJ 6989: 「一本通 3.4 例 1」Intervals会超时。
可以继续在该算法基础上使用树状数组以及并查集进行优化。
首先统计区间i，也就是 [ a i , b i ] [a_i,b_i] [ai,bi]范围内已选点数量，为区间查询，选择一个点为区间修改，这一步可以使用树状数组优化，将区间查询的复杂度从 O ( n ) O(n) O(n)降至 O ( l o g n ) O(logn) O(logn)。
从右向左遍历第i区间，寻找未选择点的过程，可以使用并查集加速。
并查集中第i点所在集合的根结点find(i)为小于等于i的第一个未选择的点。
如果选择了第j点，那么小于等于j的第一个未选择点，就是小于等于i的第一个未选择点，因此将fa[j]设为find(j-1)。遍历是，j变化为find(j)。这样可以加快遍历速度。
注：这里必须使用并查集，而不能仅使用一个数组fa表示小于等于一个点的第一个未选择点。
如果只使用fa数组，选择j点时更新方法为fa[j] = fa[j-1]。
假设存在i,i+1,i+2,i+3几个点，其中vis[i+1],vis[i+3]为真，其余为假，那么
fa[i+1]的值为i，fa[i+3]的值为i+2。
如果此时选择i+2点，将vis[i+2]设为真，fa[i+2] = fa[i+1]，值为i。
此时fa[i+3]没有变，仍然为i+2，而小于等于i+3的第一个未选择点此时为i，不是i+2。
如果使用并查集，fa[i+2] = find(i+1)，值为i。fa[i+3]为i+2，find(i+3)为i，是正确的。
优化后就可以通过以上提到的各个OJ中的问题。
解法2：差分约束
将输入的数值都增加1，最终统计区间 [ 1 , 50001 ] [1,50001] [1,50001]中选择整数的数量。
设 d i d_i di表示区间 [ 1 , i ] [1,i] [1,i]中选出数字的数量，类似前缀和， d b − d a − 1 d_b-d_{a-1} db−da−1为区间 [ a , b ] [a,b] [a,b]中选出数字的数量。
输入要求 [ a , b ] [a,b] [a,b]中至少选择 c c c个点，也就是区间 [ a , b ] [a,b] [a,b]中点的数量要求大于等于 c c c，即 d b − d a − 1 ≥ c d_{b}-d_{a-1}\ge c db−da−1≥c。
对于区间 [ i , i ] [i,i] [i,i]，区间中点的数量为 d i − d i − 1 d_i-d_{i-1} di−di−1。
- 该区间中最多有1个点，因此满足 d i − d i − 1 ≤ 1 d_i-d_{i-1}\le 1 di−di−1≤1，改写为 d i − 1 − d i ≥ − 1 d_{i-1}-d_i \ge -1 di−1−di≥−1
- 该区间中最少有0个点，即 d i − d i − 1 ≥ 0 d_i-d_{i-1} \ge 0 di−di−1≥0
以上不等式方程组构成差分约束条件。
根据差分约束建图的方法为：对于不等式 x b − x a ≥ c x_b-x_a\ge c xb−xa≥c，图中顶点a到顶点b有一条权值为c的有向边，那么
d b − d a − 1 ≥ c d_{b}-d_{a-1}\ge c db−da−1≥c：顶点a-1到顶点b有权值为c的有向边。
d i − 1 − d i ≥ − 1 d_{i-1}-d_i \ge -1 di−1−di≥−1：顶点i到顶点i-1有权值为-1的有向边。
d i − d i − 1 ≥ 0 d_i-d_{i-1} \ge 0 di−di−1≥0：顶点i-1到顶点i有权值为0的有向边。
将第0顶点设为超级源点，到每个其他顶点都有一条权值为0的有向边。
相当于存在不等式 d i − d 0 ≥ 0 d_i-d_0\ge 0 di−d0≥0，而 d 0 = 0 d_0=0 d0=0。
使用SPFA算法求以顶点0为源点的单源最长路径，求出到顶点i的最长路径长度 d i d_i di。该 d i d_i di就是满足 d i ≥ 0 d_i\ge 0 di≥0的最小值。
取 d 50001 = d 50001 − d 0 d_{50001}=d_{50001}-d_0 d50001=d50001−d0，就是区间 [ 1 , 50001 ] [1,50001] [1,50001]中的最小选点数量。
下面论证该图中一定不存在正权环：
存在顶点a-1和顶点b满足 a − 1 < b a-1<b a−1<b，如果顶点b到顶点a-1有路径，必然由【顶点i到顶点i-1的权值为-1的有向边】构成，边数为 b − a + 1 b-a+1 b−a+1，路径权值 s 1 = − ( b − a + 1 ) s1=-(b-a+1) s1=−(b−a+1)。
【顶点a-1到顶点b有权值为c的有向边】， [ a , b ] [a,b] [a,b]中最多可以选出b-a+1个数，从a-1到b的路径上可能有多条正权边，但正权边的权值加和，即路径的权值 s 2 ≤ b − a + 1 s2\le b-a+1 s2≤b−a+1
将两条路径合起来形成环，该环的权值 s 1 + s 2 ≤ 0 s1+s2\le 0 s1+s2≤0，因此不存在正权环。
【题解代码】
解法1：贪心算法+树状数组、并查集优化
#include<bits/stdc++.h>
using namespace std;
#define N 50005
struct Node
{int a, b, c;//[a, b]中选c个数bool operator < (const Node &x) const{return b < x.b;}
} a[N];
bool vis[N];//vis[i]:点i是否已被选择
int fa[N], tree[N];
void init(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)//find(x)：<=x的所有点中第一个vis为false的点
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int lowbit(int x)
{return x & -x;
}
void update(int x, int v)//vis[x] = v
{for(int i = x+1; i < N; i += lowbit(i))//x可能为0，树状数组下标从1开始 tree[i] += v;
}
int sum(int x)//vis[0]+...+vis[x]
{int res = 0;for(int i = x+1; i > 0; i -= lowbit(i))res += tree[i];return res;
}
int query(int l, int r)//vis[l]+...+vis[r]
{return sum(r)-sum(l-1);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);init(50000);int n, ans = 0;//ans：总选点数量 cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i].a >> a[i].b >> a[i].c; sort(a+1, a+1+n);for(int i = 1; i <= n; ++i){a[i].c -= query(a[i].a, a[i].b);if(a[i].c <= 0)//如果已经不需要再选点 continue;for(int j = find(a[i].b); j >= a[i].a; j = find(j)){vis[j] = true;update(j, 1);ans++;fa[j] = find(j-1);//find(j-1)是<=j-1的第一个vis为false的点的下标，fa[j]设为find(j-1)后，以后find(j)就是find(j-1) if(--a[i].c <= 0)break;}}cout << ans;return 0;
}
解法2：差分约束
#include <bits/stdc++.h>
using namespace std;
#define N 50005
struct Edge
{int v, w;
};
int n, d[N];//d[i]：1~i中选出数字的数量 d[b]-d[a-1]为a~b中选出数字的数量
bool inQue[N];
vector<Edge> edge[N];
void spfa(int sv)
{queue<int> que;memset(d, 0xc0, sizeof(d));d[sv] = 0;inQue[sv] = true;que.push(sv);while(!que.empty()){int u = que.front();que.pop();inQue[u] = false;for(Edge e : edge[u]){int v = e.v, w = e.w;if(d[v] < d[u]+w){d[v] = d[u]+w;if(!inQue[v]){inQue[v] = true;que.push(v);}}}}
}
int main()
{int a, b, c;cin >> n;for(int i = 1; i <= n; ++i){cin >> a >> b >> c;//a~b中选出数字的数量大于等于c d[b]-d[a-1] >= ca++, b++;//输入的数字增加1，使得数字范围为1~50001 edge[a-1].push_back(Edge{b, c});//d[b]-d[a-1] >= c}for(int i = 1; i <= 50001; ++i){//i~i中有最少0个数字，最多1个数字，即 0 <= d[i]-d[i-1] <= 1edge[i].push_back(Edge{i-1, -1});//d[i-1]-d[i] >= -1edge[i-1].push_back(Edge{i, 0});//d[i]-d[i-1] >= 0edge[0].push_back(Edge{i, 0});//d[i]-d[0] >= 0 顶点0为超级源点 }spfa(0);cout << d[50001];return 0;
}