首页 > 代码库 > POJ 1201 Intervals
POJ 1201 Intervals
Intervals
Time Limit: 2000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 120164-bit integer IO format: %lld Java class name: Main
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
53 7 38 10 36 8 11 3 110 11 1
Sample Output
6
Source
Southwestern Europe 2002
解题：差分约束系统。参见书山有路，学海无涯
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 50010;18 struct arc{19 int to,w,next;20 arc(int x = 0,int y = 0,int z = 0){21 to = x;22 w = y;23 next = z;24 }25 };26 int n,tot,head[maxn],theMin,theMax,d[maxn];27 arc e[maxn<<2];28 int q[maxn<<4],he,tail;29 bool in[maxn];30 void add(int u,int v,int w){31 e[tot] = arc(v,w,head[u]);32 head[u] = tot++;33 }34 int spfa(){35 for(int i = theMin; i <= theMax; i++){36 in[i] = false;37 d[i] = -INF;38 }39 d[theMin] = 0;40 he = tail = 0;41 q[tail++] = theMin;42 while(he < tail){43 int u = q[he++];44 in[u] = false;45 for(int i = head[u]; ~i; i = e[i].next){46 if(d[e[i].to] < d[u]+e[i].w){47 d[e[i].to] = d[u]+e[i].w;48 if(!in[e[i].to]){49 in[e[i].to] = true;50 q[tail++] = e[i].to;51 }52 }53 }54 }55 return d[theMax];56 }57 int main() {58 int u,v,w;59 while(~scanf("%d",&n)){60 memset(head,-1,sizeof(head));61 theMin = INF;62 theMax = -INF;63 for(int i = tot = 0; i < n; i++){64 scanf("%d %d %d",&u,&v,&w);65 add(u,v+1,w);66 theMin = min(theMin,u);67 theMax = max(theMax,v+1);68 }69 for(int i = theMin; i < theMax; i++){70 add(i,i+1,0);71 add(i+1,i,-1);72 }73 printf("%d\n",spfa());74 }75 return 0;76 }
POJ 1201 Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。