首页 > 代码库 > BZOJ 1828: [Usaco2010 Mar]balloc 农场分配
BZOJ 1828: [Usaco2010 Mar]balloc 农场分配
Description
Input
第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行： 第i+N+1行表示2个整数 A_i和B_i
Output
* 第一行： 一个整数表示最多能够被满足的要求数
题解：
将请求按右端点排序，然后依次添加，用线段树判断是否能添加，不能的放弃。统计个数即可。
代码：
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;int minn[100005*4];int mark[100005*4];int c[100005];void pd(int o){ if(mark[o]){ minn[o<<1]-=mark[o]; minn[o<<1|1]-=mark[o]; mark[o<<1]+=mark[o]; mark[o<<1|1]+=mark[o]; mark[o]=0; }}void insert(int o,int l,int r,int L,int R){ if(l==L&&r==R){ mark[o]+=1; minn[o]-=1; return; }else{ pd(o); int m=(L+R)>>1; if(r<=m) insert(o<<1,l,r,L,m); else if(l>m) insert(o<<1|1,l,r,m+1,R); else insert(o<<1,l,m,L,m),insert(o<<1|1,m+1,r,m+1,R); minn[o]=min(minn[o<<1],minn[o<<1|1]); }}void build(int o,int l,int r){ if(l==r){ minn[o]=c[l]; }else{ int m=(l+r)>>1; build(o<<1,l,m); build(o<<1|1,m+1,r); minn[o]=min(minn[o<<1],minn[o<<1|1]); }}bool ok;void ask(int o,int l,int r,int L,int R){ if(l==L&&r==R) ok&=(minn[o]>0); else{ pd(o); int m=(L+R)>>1; if(r<=m) ask(o<<1,l,r,L,m); else if(l>m) ask(o<<1|1,l,r,m+1,R); else ask(o<<1,l,m,L,m),ask(o<<1|1,m+1,r,m+1,R); }}struct node{ int a,b;}q[100005];bool cmp(node a,node b){ return a.b<b.b;}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); } for(int i=0;i<m;i++){ scanf("%d%d",&q[i].a,&q[i].b); } sort(q,q+m,cmp); int ans=0; build(1,1,n); for(int i=0;i<m;i++){ ok=1;ask(1,q[i].a,q[i].b,1,n); if(ok){ ans++; insert(1,q[i].a,q[i].b,1,n); } } printf("%d\n",ans); return 0;}
BZOJ 1828: [Usaco2010 Mar]balloc 农场分配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。