362. 区间 - AcWing题库
给定 nn 个区间 [ai,bi][ai,bi] 和 nn 个整数 cici。
你需要构造一个整数集合 ZZ,使得 ∀i∈[1,n]∀i∈[1,n],ZZ 中满足 ai≤x≤biai≤x≤bi 的整数 xx 不少于 cici 个。
求这样的整数集合 ZZ 最少包含多少个数。
输入格式
第一行包含整数 nn。
接下来 nn 行,每行包含三个整数 ai,bi,ciai,bi,ci。
输出格式
输出一个整数表示结果。
数据范围
1≤n≤500001≤n≤50000,
0≤ai,bi≤500000≤ai,bi≤50000,
0≤ci≤bi−ai+10≤ci≤bi−ai+1
输入样例:
复制代码
1
2
3
4
5
6
75 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
输出样例:
复制代码
16
题解:
我们利用前缀和的思想,s[i]为0~当前为最少需要多少数才能满足条件
由于前缀和一般不能占用下标为0的id,为了方便操作,我们范围变成1~50001,枚举a和b是都++即可,相对还是不变的
接着我们来判断一下不等式
1.si >= si-1 由于是前缀和
2.si - si-1 <= 1 顶多会多一个数
变形一下si-1 >= si - 1
3.sb - sa-1 >= c 根据题意
变形一下
sb >= sa-1 + c
接着连接路径,由于求的是最小值,所以求最长路即可
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include<iostream> #include<cstring> #include<queue> #include<stack> using namespace std; const int N = 3e5 + 10; #define int long long int h[N],w[N],e[N],ne[N],idx; int dis[N]; int st[N]; void add(int a,int b,int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } void spfa() { queue<int> q; st[0] = 1; dis[0] = 0; q.push(0); while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for(int i = h[t];i != -1;i = ne[i]) { int j = e[i]; if(dis[j] < dis[t] + w[i]) { dis[j] = dis[t] + w[i]; if(!st[j]) { q.push(j); st[j] = 1; } } } } } signed main() { int n; cin >> n; memset(h,-1,sizeof h); memset(dis,-0x3f,sizeof dis); for(int i = 1;i <= 50001;i++) { add(i-1,i,0); add(i,i-1,-1); } for(int i = 1;i <= n;i++) { int a,b,c; cin >> a >> b >> c; a++,b++; add(a-1,b,c); } spfa(); cout << dis[50001]; }
最后
以上就是勤劳火最近收集整理的关于362. 区间(差分约束)的全部内容,更多相关362.内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复