362. 区间(差分约束)

89 阅读 0 评论 59 点赞

我是靠谱客的博主勤劳火，这篇文章主要介绍362. 区间(差分约束)，现在分享给大家，希望可以做个参考。

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
6

题解:

我们利用前缀和的思想,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];
}