Intervals
Time Limit: 2000MS Memory Limit: 65536K
Description
You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.
Write a program that:
reads the number of intervals, their end points 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 <= 50000) – 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 <= 50000 and 1 <= ci <= bi - ai+1.
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
Source
Southwestern Europe 2002
/*
又回过头来看了一下半年前学的差分约束.
感觉自己还是弱弱的.
由约束条件可得
(1)dis[y+1]-dis[x]>=z.
(2)0<=dis[i]-dis[i-1]<=1.
因为是跑最长路.
所以要把(2)式拆成
dis[i]-dis[i-1]>=0.
dis[i-1]-dis[i]>=-1.
spfa松弛即可.
*/
#include<cstring>
#include<cstdio>
#include<queue>
#define MAXN 50001
using namespace std;
struct data{int v,next,x;}e[MAXN*3];
int n,m,head[MAXN],dis[MAXN],cut,maxv,maxn,minn=1e6;
bool b[MAXN];
void add(int u,int v,int x)
{
e[++cut].v=v;
e[cut].x=x;
e[cut].next=head[u];
head[u]=cut;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void spfa()
{
memset(dis,-127/3,sizeof dis);
queue<int>q;q.push(minn);dis[minn]=0;
while(!q.empty())
{
int u=q.front();q.pop();b[u]=false;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]<dis[u]+e[i].x)
{
dis[v]=dis[u]+e[i].x;
if(!b[v]) b[v]=true,q.push(v);
}
}
}
return ;
}
int main()
{
int x,y,z;
m=read();
for(int i=1;i<=m;i++)
{
x=read(),y=read(),z=read();y++;
add(x,y,z);
minn=min(minn,x),maxn=max(maxn,y);
}
for(int i=minn;i<=maxn;i++) add(i,i+1,0),add(i+1,i,-1);
spfa();
printf("%d",dis[maxn]);
return 0;
}/*
我们也可以跑最短路.
由约束条件可得
(1)dis[x]-dis[y+1]<=z.
(2)0<=dis[i]-dis[i-1]<=1.
因为是跑最短路.
所以要把(2)式拆成
dis[i]-dis[i-1]<=1.
dis[i-1]-dis[i]<=0.
然后从终点跑,最后将答案取反.
*/
#include<cstring>
#include<cstdio>
#include<queue>
#define MAXN 50001
using namespace std;
struct data{int v,next,x;}e[MAXN*3];
int n,m,head[MAXN],dis[MAXN],cut,maxv,maxn,minn=1e6;
bool b[MAXN];
void add(int u,int v,int x)
{
e[++cut].v=v;
e[cut].x=x;
e[cut].next=head[u];
head[u]=cut;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void spfa()
{
memset(dis,127/3,sizeof dis);
queue<int>q;q.push(maxn);dis[maxn]=0;
while(!q.empty())
{
int u=q.front();q.pop();b[u]=false;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].x)
{
dis[v]=dis[u]+e[i].x;
if(!b[v]) b[v]=true,q.push(v);
}
}
}
return ;
}
int main()
{
int x,y,z;
m=read();
for(int i=1;i<=m;i++)
{
x=read(),y=read(),z=read();y++;
add(y,x,-z);
minn=min(minn,x),maxn=max(maxn,y);
}
for(int i=minn;i<=maxn;i++) add(i,i-1,0),add(i,i+1,1);
spfa();
printf("%d",-dis[minn]);
return 0;
}