【Problem Description】 You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn. Write a program that: 1.reads the number of intervals, their endpoints and integers c1, …, cn from the standard input, 2.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, 3.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 【解题报告】 这道题的大意就是给你很多区间[ai,bi]，并且对于每一个区间至少需要分出ci个点，问你对于这些所有的ai和bi，总共最少需要多少个点满足条件。 我们令数组sum[i]存储[1,i]的区间内用了多少个点，那么我们可以列出以下不等式： sum[b]-sum[a-1]>=c; sum[i]-sum[i-1]>=0; sum[i]-sum[i-1]<=1;==>sum[i-1]-sum[i]>=-1; 此外，我们需要在每一次的ai,bi中选出最小的ai,最大的bi作为这个图的起点和终点。图建好之后跑一边最长路SPFA就可以了。 代码如下：
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int N=50000; const int INF=0x7fffffff; int head[N+5],num; int dis[N+5],flag[N+5]; queue<int> q; int n; int vmax,vmin=INF; struct edge { int u,v,w; int next; edge(){next=-1;} }ed[4*N+5]; void build(int u,int v,int w) { ed[++num].v=v; ed[num].w=w; ed[num].next=head[u]; head[u]=num; } int SPFA(int s,int e) { for(int i=s;i<=e;i++) dis[i]=-INF,flag[i]=0; q.push(s); dis[s]=0; flag[s]=1; while(!q.empty()) { int u=q.front();q.pop(); flag[u]=0; for(int i=head[u];i!=-1;i=ed[i].next) { int v=ed[i].v; if(dis[v]<dis[u]+ed[i].w) { dis[v]=dis[u]+ed[i].w; if(!flag[v]) { flag[v]=1; q.push(v); } } } } return dis[e]; } int main() { while(~scanf("%d",&n)) { memset(head,-1,sizeof(head)); num=0,vmax=0,vmin=INF; while(n--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); vmax=max(b,vmax); vmin=min(a-1,vmin); build(a-1,b,c); } for(int i=vmin;i<=vmax;i++) { build(i-1,i,0); build(i,i-1,-1); } printf("%d\n",SPFA(vmin,vmax)); } return 0; }