首页 > 代码库 > poj1201(二分+线段树)或(差分约束系统)
poj1201(二分+线段树)或(差分约束系统)
题意:数轴上每个位置为0或是1,给n(1 <= n <= 50000)个区间[ai, bi],每个区间内至少有 ci 个1.0 <= ai <= bi <= 50000,1 <= ci <= bi - ai+1。问数轴上至少有多少个1可以满足要求。
解法1:现将区间按右端点排序,然后每个区间内的点尽量往右边放,这样子可以照顾到以后的。在找每个区间的放法时,线段树查询区间1的个数,二分查找要放的后缀位置,然后将整个区间后缀全部涂上1.总复杂度是nlognlogn。网上没找到有人这么做的,但确实可以。
解法2: 将每个数轴的前缀的1的数量当做一个点。然后[ai,bi]之间有ci个点,就是点ai-1到点bi有个ci的边。然后每个位置最少0个1,最多1个1.所以ai 到 ai+1有个0长度的边,ai+1到ai有个-1长度的边。 然后就是求左端点到右端点的最长路了。
解法一代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=50010; const LL INF=0x3FFFFFFF; struct node { int l,r; node* pl,*pr; bool same; int sum; } nodes[Max*3]; int tot=0; int n=0; void build(node* p,int left,int right) { p->l=left; p->r=right; p->sum=0; p->same=0; if(left==right) return ; int middle=(left+right)/2; tot++; p->pl=nodes+tot; build(p->pl,left,middle); tot++; p->pr=nodes+tot; build(p->pr,middle+1,right); } void push_down(node* p) { int middle=(p->r+p->l)/2; p->pl->same=1; p->pl->sum=middle-p->l+1; p->pr->same=1; p->pr->sum=p->r-middle; p->same=0; } void pushup(node* p) { p->sum=p->pr->sum+p->pl->sum; } void update(node* p,int left,int right) { if(p->l==p->r) { p->same=1; p->sum=1; return ; } if(p->l==left&&p->r==right) { p->same=1; p->sum=right-left+1; return ; } if(p->same) push_down(p); int middle=(p->r+p->l)/2; if(left>middle) update(p->pr,left,right); else if(right<=middle) update(p->pl,left,right); else { update(p->pl,left,middle); update(p->pr,middle+1,right); } pushup(p); } int query(node* p,int left,int right) { if(right<left) return 0; if(p->l==left&&p->r==right) return p->sum; if(p->same) push_down(p); int middle=(p->r+p->l)/2; if(left>middle) return query(p->pr,left,right); else if(right<=middle) return query(p->pl,left,right); else return query(p->pl,left,middle)+query(p->pr,middle+1,right); } struct line { int x,y; int c; } lines[Max]; bool operator<(const line& a,const line& b) { if(a.y!=b.y) return a.y<b.y; return a.x<b.x; } void solve(int a,int b,int c) { if(query(nodes,a,b)>=c) return ; int left=a,right=b; while(left<=right) { int middle=(left+right)/2; if(query(nodes,a,middle)+b-middle>=c) left=middle+1; else right=middle-1; } ///cout<<left<<endl; update(nodes,left,b); } int main() { while(cin>>n) { tot=0; build(nodes,0,Max-1); for(int i=0; i<n; i++) scanf("%d%d%d",&lines[i].x,&lines[i].y,&lines[i].c); sort(lines,lines+n); for(int i=0; i<n; i++) { solve(lines[i].x,lines[i].y,lines[i].c); //cout<<lines[i].x<<" "<<lines[i].y<<endl; // cout<<" "<<query(nodes,1,Max-1)<<endl; } cout<<query(nodes,0,Max-1)<<endl; } return 0; }
解法2代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=50010; const LL INF=0x3FFFFFFF; struct edge { int u,v; int next; int len; } edges[Max*3]; int tot=0; int head[Max]; void add(int u,int v,int c) { edges[tot].u=u; edges[tot].v=v; edges[tot].len=c; edges[tot].next=head[u]; head[u]=tot++; } int dist[Max]; int n; int mi=Max; int ma=0; int que[Max*10]; bool rem[Max]; void spfa() { memset(rem,0,sizeof rem); dist[mi]=0; rem[mi]=1; int left=0; int right=1; que[0]=mi; while(left<right) { int t=que[left++]; rem[t]=0; for(int i=head[t]; i!=-1; i=edges[i].next) { int ne=edges[i].v; if(dist[ne]<dist[t]+edges[i].len) { dist[ne]=dist[t]+edges[i].len; if(!rem[ne]) { que[right++]=ne; rem[ne]=1; } } } } } int main() { cin>>n; memset(head,-1,sizeof head); for(int i=0; i<n; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); a++;b++; mi=min(mi,a-1); ma=max(ma,b); add(a-1,b,c); } for(int i=mi; i<=ma; i++) { add(i,i+1,0); add(i+1,i,-1); dist[i]=-INF; } spfa(); cout<<dist[ma]<<endl; return 0; }
poj1201(二分+线段树)或(差分约束系统)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。