You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
> reads the number of intervals, their endpoints and integers c1, ..., cn from the standard input,
> computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i = 1, 2, ..., n,
> writes the answer to the standard output
Input
The first line of the input contains an integer n (1 <= n <= 50 000) - the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <= ci <= bi - ai + 1.
Process to the end of file.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
题意:
给定n个区间,每个区间内至少选中c个点,问整个数轴上至少选中多少个点
思路:
前几个月学的,比赛的时候竟然没有看出来qwq 枯了
当时写的博客https://blog.csdn.net/weixin_43871207/article/details/102484592
差分约束典型例题
设[0,i]共选中了d[i]个点,可以得出d[b] - d[a - 1] >= c,对于每个不等式建立一条从a - 1到b,权值为ci的边。
注意隐含条件:每个点至少选0次(即不选),至多选1次,所以除了对输入的多个区间建边外,还有d[i] - d[i - 1] >= 0 和d[i] - d[i -1] <= 1,将第二个不等式转化为上面的形式即d[i - 1] - d[i] >= -1
防止数组越界,将所有数+1
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int inf = 0xc0c0c0c0;
const int N = 5e4 + 20;
int tot, n, r;
int dis[N], vis[N], head[N], num[N];
struct Edge
{
int u, v, w, next;
}edge[10 * N];
void add(int a, int b, int c)
{
edge[tot].u = a;
edge[tot].v = b;
edge[tot].w = c;
edge[tot].next = head[a];
head[a] = tot++;
}
bool spfa(int s)
{
queue<int>q;
for(int i = 0; i <= r + 2; ++i)
dis[i] = inf;
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
q.push(s);
dis[s] = 0;
while(!q.empty())
{
int pos = q.front();
q.pop();
vis[pos] = 0;
num[pos]++;
for(int i = head[pos]; i != -1; i = edge[i].next)
{
if(dis[edge[i].v] < dis[edge[i].u] + edge[i].w)
{
dis[edge[i].v] = dis[edge[i].u] + edge[i].w;
if(!vis[edge[i].v])
{
vis[edge[i].v] = 1;
q.push(edge[i].v);
if(num[edge[i].v] >= r)
return 0;
}
}
}
}
return 1;
}
int main()
{
int a, b, c;
while(~scanf("%d", &n))
{
tot = 0;
memset(edge, 0, sizeof(edge));
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; ++i)
{
scanf("%d%d%d", &a, &b, &c);
r = max(b, r); ///最大值
add(a, b + 1, c);
}
for(int i = 2; i <= r + 1; ++i)
{
add(i - 1, i, 0);
add(i, i - 1, -1);
}
bool flag = spfa(1); ///是否有正环(在本题中并不重要)
if(flag && dis[r + 1] == inf)
flag = 0;
if(flag)
{
cout<<dis[r + 1]<<'\n';
}
}
return 0;
}