Intervals
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 22996 | Accepted: 8678 |
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
这题是我们今天的差分约束作业之一。。应该是最水的一道了。。课堂上思路就已经讲过了。
我们记是s[i] = a[0]+a[1]+a[2]+....+a[i]即为a的前缀和那么对于a到b的区间内个数大于c就可以列出一个式子：s[b]-s[a-1]>=c。
因为题目限制0<=a[i]<=1,所以0<=s[i]-s[i-1]<=1,将其拆开可以得到两个式子s[i]-s[i-1]>=0 && s[i-1]-s[i]>=-1，然后我们就可以根据这个连边，因为题目求最小值所以用最长路算法。
细节：因为a可以等于0，所以a-1可能等于负数，所以可以给所有的下标+1。。#include <cstdio>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct data{int x,y,s,next;} e[2000010];
int dis[500100],v[500010],head[500010],Min,Max,n,cnt,q[2000010],h,t,x,y,s,c;
void Insert(int x,int y,int s){
e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
e[cnt].next = head[x];head[x] = cnt;
}
void Spfa(){
for (int i=Min;i<=Max;i++) dis[i] = -1e9;
dis[Min] = 0;q[1] = Min;h = 0;t = 1;v[Min] = 1;
while (h<t){
int now = q[++h];
for (int i=head[now];i;i=e[i].next)
if (dis[now]+e[i].s>dis[e[i].y]){
dis[e[i].y] = dis[now]+e[i].s;
if (!v[e[i].y]) {v[e[i].y] = 1;q[++t] = e[i].y;}
}
v[now] = 0;
}
}
int main(){
scanf("%d",&n);
Min = 500010;
for (int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&c);
Insert(x,y+1,c);
Min = min(x,Min);
Max = max(y+1,Max);
}
for (int i=Min;i<Max;i++){
Insert(i,i+1,0);
Insert(i+1,i,-1);
}
Spfa();
printf("%d",dis[Max]);
}
评论 (0)
