Intervals
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 26028 | Accepted: 9952 |
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.
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
题意：有n个区间，每个区间有3个值，ai，bi，ci代表，在区间[ai,bi]上至少要选择ci个整数点，ci可以在区间内任意取不重复的点
现在要满足所有区间的自身条件，问最少选多少个点
一段区间，想到前缀和处理选的个数
每个前缀和建一个点
s[b]-s[a-1]>=c
同时要满足前缀和的性质，即：
s[i]-s[i-1]>=0
s[i]-s[i-1]<=1
最小值，按>=建图跑最长路
注意区间范围0..n，读入时改成了1...n+1(n)
但是0节点也是（前缀和！）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=5e4+,M=15e4+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,a,b,c;
struct edge{
int v,ne;
double w;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
int q[N],head,tail,inq[N],num[N],d[N];
inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}
bool spfa(){
head=tail=;
memset(inq,,sizeof(inq));
memset(num,,sizeof(num));
for(int i=;i<=n;i++) q[tail++]=i,inq[i]=,d[i]=;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]<d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
inq[v]=;
if(++num[v]>n) return true;
if(d[v]>d[q[head]]) head--,lop(head),q[head]=v;
else q[tail++]=v,lop(tail);
}
}
}
}
return false;
}
int main(){
m=read();
for(int i=;i<=m;i++){
a=read()+;b=read()+;c=read();n=max(n,b);
ins(a-,b,c);
}
for(int i=;i<=n;i++) ins(i-,i,),ins(i,i-,-);
spfa();
printf("%d",d[n]);
}