Intervals
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 22503 | Accepted: 8506 |
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.
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.
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]表示集合中小于等于i的元素个数， u v w s[v]-s[u-1]>=w;
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <sstream>
#include <iomanip>
using namespace std;
const int INF=0x4fffffff;
const int EXP=1e-;
const int MS=; struct edge
{
int u,v,w;
}edges[*MS]; int maxv,minv;
int dis[MS];
int esize,n; bool bellman()
{
memset(dis,,sizeof(dis));
bool flag=true;
int cnt=;
while(flag)
{
flag=false; //表示没有更新了 if(cnt++>n) //更新次数大于n-1,
return false;
for(int i=;i<esize;i++)
{
if(dis[edges[i].u]+edges[i].w<dis[edges[i].v])
{
dis[edges[i].v]=dis[edges[i].u]+edges[i].w;
flag=true;
}
} //0<=s[i]-s[i-1]<=1 这些边可以不用存储 // i-1 -->i 1 for(int i=minv;i<=maxv;i++)
{
if(dis[i-]+<dis[i])
{
dis[i]=dis[i-]+;
flag=true;
}
} // i--> i-1 0 for(int i=maxv;i>=minv;i--)
{
if(dis[i]<dis[i-])
{
dis[i-]=dis[i];
flag=true;
}
}
}
return true;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
int u,v,w;
esize=;
maxv=;
minv=INF;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
// s[i]表示集合中小于等于i的元素个数
//s[v]-s[u-1]>=w; v->u-1 -w;
edges[esize].u=v;
edges[esize].v=u-;
edges[esize++].w=-w;
if(v>maxv)
maxv=v;
if(u<minv)
minv=u;
}
bellman();
printf("%d\n",dis[maxv]-dis[minv-]);
}
return ;
}