首页 > 代码库 > poj 1716 Integer Intervals
poj 1716 Integer Intervals
Integer Intervals
http://poj.org/problem?id=1716
| Time Limit: 1000MS | Memory Limit: 10000K | |
Description
An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.
Input
The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.
Output
Output the minimal number of elements in a set containing at least two different integers from each interval.
Sample Input
43 62 40 24 7
Sample Output
4
Source
CEOI 1997
题目大意：在指定的几个区间中选出最少的数，使每个区间至少包含这些数中的2个，求最少多少数
解法一：贪心
把所有的区间按右端点从小到大排序
初始时，假设这两个数x，y为第一个区间最右边的2个数，x<=y，ans=2
如果下一个区间左端点<=x，跳过
如果下一个区间的左端点在>x 且<=y，令x=y，y=当前区间右端点，ans++
如果下一个区间的左端点>y x，y为当前区间最右边的两个数，ans+2
#include<cstdio>#include<algorithm>using namespace std;int n,ans;struct node{ int a,b;}e[10001];bool cmp(node p,node q){ return p.b<q.b;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&e[i].a,&e[i].b); sort(e+1,e+n+1,cmp); int x=e[1].b-1,y=x+1; ans=2; for(int i=2;i<=n;i++) { if(e[i].a<=x) continue; if(e[i].a<=y) {x=y;y=e[i].b;ans++;continue;} x=e[i].b-1;y=x+1;ans+=2; } printf("%d",ans);}
解法二：差分约束
某大佬差分约束详解：http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
若d[x]-d[y]<=/>= c ,则由y向x连一条权值为c的边
设d[i]为从1号点到i最少选出的数的个数
根据题目要求，对于区间[l,r],得约束条件1:d[r]-d[l-1]>=2
为保证连续性，隐含约束条件2：0<=d[i]-d[i-1]<=1
即每个点要么不选，要么只能选一次
设总区间[s,t]
那么目的就是 d[t]-d[s]>=ans
即d[t]>=ans+d[s]，所以spfa跑最长路
因为题目中，输入数据端点可能有0，所以我们将所有的数整体后移一位
#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#define N 10002using namespace std;int n,minn=10002,maxn;queue<int>q;struct node{ int to,next,w;}e[N*3];int dis[N],front[N],tot;bool v[N];void add(int u,int v,int w){ e[++tot].to=v;e[tot].next=front[u];front[u]=tot;e[tot].w=w;}int main(){ int x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y);y++; add(x,y,2); minn=min(x,minn);maxn=max(maxn,y); } for(int i=minn;i<maxn;i++) { add(i,i+1,0);add(i+1,i,-1); } memset(dis,-1,sizeof dis); q.push(minn);v[minn]=true;dis[minn]=0; while(!q.empty()) { int now=q.front();q.pop();v[now]=false; for(int i=front[now];i;i=e[i].next) { int to=e[i].to; if(dis[to]<dis[now]+e[i].w) { dis[to]=dis[now]+e[i].w; if(!v[to]) { v[to]=true; q.push(to); } } } } printf("%d",dis[maxn]);}
一个错误：N=10001，因为全体后移了一位，所以N最少是10002
poj 1716 Integer Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。