当前位置：首页 > news >正文

信息学奥赛一本通 1509：【例 1】Intervals | OpenJudge 百练 1201:Intervals

news 来源：原创 2025/6/25 20:08:38

【题目链接】

ybt 1509：【例 1】Intervals
OpenJudge 百练 1201:Intervals

【题目考点】

1. 贪心算法树状数组并查集

2. 差分约束算法

【解题思路】

解法1：贪心算法+树状数组、并查集优化

该题属于区间选点问题，ybt 1324：【例6.6】整数区间是给定一些区间，选择一些点使得每个区间范围内至少有1个点。
本题为：给定一些区间，选择一些点使得每个区间范围内至少有给定数量的点。

贪心选择：对每个区间，如果还需要选点，则尽量从区间右侧选点。
所有区间按照右端点 $b$ 从小到大排序，排序后第i区间范围为 $a_i, b_i]$ ，其中需要至少选择 $c_i$ 个点。
贪心选择的具体解释：

如果该区间中已经选择点的数量大于等于 $c_i$ ，则不需要再选点。
如果该区间中已经选择点的数量小于 $c_i$ ，则从 $b_i$ 到 $a_i$ 从大到小遍历每个点，遇到未选择的点就选择该点，直到选够 $c_i$ 个点。

贪心选择性质的证明：

证明存在最优解包含第一次的贪心选择
第一次的贪心选择为：在 $a_1,b_1]$ 中选择区间 $b_1-c_1+1, b_1]$ 中的整数点，共 $c_1$ 个点。
反证法：假设所有最优解都不包含第一次的贪心选择
也就是说在 $a_1, b_1-c_1]$ 选择了一些点，而 $b_1-c_1+1, b_1]$ 中存在未被选择的点。设在 $a_1, b_1-c_1]$ 中选择了点 $G$ ，而 $b_1-c_1+1, b_1]$ 中点 $F$ 未被选择。
现在不选择点 $G$ 转而选择点 $F$ ，第2、第3等后面的区间中已选择的点可能会增加，也可能不变。每个区间的选点数量都满足要求，总选点数量不变。因此这样变换选择点后，此时的选点方案仍然是最优解。
将在 $a_1, b_1-c_1]$ 中选择的所有点都去掉，转而在 $b_1-c_1+1, b_1]$ 中选择相同数量的点，最后选择的点就是 $b_1-c_1+1, b_1]$ 中的每个点，这也就是进行了贪心选择，这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖，原命题得证。
假设最优解包含前k次的贪心选择，证明存在最优解包含第k+1次的贪心选择：
证明过程与第1点的证明过程相似，不再赘述。

具体实现：
设vis数组，vis[i]表示第i点是否已被选择。
对于每个区间，先遍历整个区间，统计出已选点数量，也就是求出待选择点的数量。

如果待选择点的数量为0，就看下一个区间。
否则，从区间右端点开始，向前遍历，遇到未选择的点，就选择一个点，直到待选择点的数量为0。统计选点总数量，就是问题结果。

该算法的复杂度达到了 $O(n^2)$ ，尽管可以通过ybt 1509与OpenJudge 百练 1201的测试点，但在LOJ10087. 「一本通 3.4 例 1」Intervals，以及MYOJ 6989: 「一本通 3.4 例 1」Intervals会超时。
可以继续在该算法基础上使用树状数组以及并查集进行优化。
首先统计区间i，也就是 $a_i,b_i]$ 范围内已选点数量，为区间查询，选择一个点为区间修改，这一步可以使用树状数组优化，将区间查询的复杂度从 $O (n)$ 降至 $O (l o g n)$ 。
从右向左遍历第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]$ 中选择整数的数量。
设 $d_i$ 表示区间 $[1, i]$ 中选出数字的数量，类似前缀和， $d_b-d_{a-1}$ 为区间 $[a, b]$ 中选出数字的数量。
输入要求 $[a, b]$ 中至少选择 $c$ 个点，也就是区间 $[a, b]$ 中点的数量要求大于等于 $c$ ，即 $d_{b}-d_{a-1}\ge c$ 。
对于区间 $[i, i]$ ，区间中点的数量为 $d_i-d_{i-1}$ 。

该区间中最多有1个点，因此满足 $d_i-d_{i-1}\le 1$ ，改写为 $d_{i-1}-d_i \ge -1$
该区间中最少有0个点，即 $d_i-d_{i-1} \ge 0$

以上不等式方程组构成差分约束条件。
根据差分约束建图的方法为：对于不等式 $x_b-x_a\ge c$ ，图中顶点a到顶点b有一条权值为c的有向边，那么
$d_{b}-d_{a-1}\ge c$ ：顶点a-1到顶点b有权值为c的有向边。
$d_{i-1}-d_i \ge -1$ ：顶点i到顶点i-1有权值为-1的有向边。
$d_i-d_{i-1} \ge 0$ ：顶点i-1到顶点i有权值为0的有向边。

将第0顶点设为超级源点，到每个其他顶点都有一条权值为0的有向边。
相当于存在不等式 $d_i-d_0\ge 0$ ，而 $d_0=0$ 。
使用SPFA算法求以顶点0为源点的单源最长路径，求出到顶点i的最长路径长度 $d_i$ 。该 $d_i$ 就是满足 $d_i\ge 0$ 的最小值。
取 $d_{50001}=d_{50001}-d_0$ ，就是区间 $[1, 50001]$ 中的最小选点数量。

下面论证该图中一定不存在正权环：

存在顶点a-1和顶点b满足 $a - 1 < b$ ，如果顶点b到顶点a-1有路径，必然由【顶点i到顶点i-1的权值为-1的有向边】构成，边数为 $b - a + 1$ ，路径权值 $s 1 = - (b - a + 1)$ 。
【顶点a-1到顶点b有权值为c的有向边】， $[a, b]$ 中最多可以选出b-a+1个数，从a-1到b的路径上可能有多条正权边，但正权边的权值加和，即路径的权值 $s2\le b-a+1$
将两条路径合起来形成环，该环的权值 $s1+s2\le 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;
}

【题目链接】

【题目考点】

1. 贪心算法 树状数组 并查集

2. 差分约束算法

【解题思路】

解法1：贪心算法+树状数组、并查集优化

解法2：差分约束

【题解代码】

解法1：贪心算法+树状数组、并查集优化

解法2：差分约束

相关文章：

1. 贪心算法树状数组并查集