Luogu P1607 庙会班车【线段树】By cellur925

题目传送门

据说可以用贪心做？算了算了...我都不会贪...。

---

 

开始想的是用线段树，先建出一颗空树，然后输进区间操作后就维护最大值，显然开始我忽视了班车的容量以及可以有多组奶牛坐在一起的信息。

我们肯定想要有更多的区间被选中，根据线段覆盖问题的套路，我们要优先选结束位置最小的，能选就选，但是需要判断下能不能选，就是比较下当前区间最大值和容量的关系，尽量加上，进行修改。说白了就是在维护带修改的区间最大值。

Code

1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 int k,n,c,ans; 7 struct moo{ 8 int f,t,sum; 9 }cow[50090]; 10 struct SegmentTree{ 11 int l,r,val,lazy; 12 }t[20090*4]; 13 14 bool cmp(moo a,moo b) 15 { 16 return a.t<b.t; 17 } 18 19 void build(int p,int l,int r) 20 { 21 t[p].l=l,t[p].r=r; 22 if(l==r) return ; 23 int mid=(l+r)>>1; 24 build(p*2,l,mid); 25 build(p*2+1,mid+1,r); 26 } 27 28 void update(int p) 29 { 30 if(!t[p].lazy) return ; 31 if(t[p].l==t[p].r) return ; 32 t[p*2].val+=t[p].lazy; 33 t[p*2+1].val+=t[p].lazy; 34 t[p*2].lazy+=t[p].lazy; 35 t[p*2+1].lazy+=t[p].lazy; 36 t[p].lazy=0; 37 } 38 39 void change(int p,int l,int r,int x) 40 { 41 update(p); 42 if(t[p].l==l&&t[p].r==r) 43 { 44 t[p].val+=x; 45 t[p].lazy+=x; 46 return ; 47 } 48 int mid=(t[p].l+t[p].r)>>1; 49 if(l>mid) change(p*2+1,l,r,x); 50 else if(r<=mid) change(p*2,l,r,x); 51 else change(p*2,l,mid,x),change(p*2+1,mid+1,r,x); 52 t[p].val=max(t[p*2].val,t[p*2+1].val); 53 } 54 55 int ask(int p,int l,int r) 56 { 57 update(p); 58 if(t[p].l==l&&t[p].r==r) return t[p].val; 59 int mid=(t[p].l+t[p].r)>>1; 60 if(l>mid) return ask(p*2+1,l,r); 61 else if(r<=mid) return ask(p*2,l,r); 62 else return max(ask(p*2,l,mid),ask(p*2+1,mid+1,r)); 63 } 64 65 int main() 66 { 67 scanf("%d%d%d",&k,&n,&c); 68 for(int i=1;i<=k;i++) 69 scanf("%d%d%d",&cow[i].f,&cow[i].t,&cow[i].sum); 70 sort(cow+1,cow+1+k,cmp); 71 build(1,1,n); 72 for(int i=1;i<=k;i++) 73 { 74 int sta=ask(1,cow[i].f,cow[i].t),res=0; 75 if(sta>=c) continue; 76 if(sta+cow[i].sum<=c) res=cow[i].sum; 77 else res=c-sta; 78 ans+=res; 79 change(1,cow[i].f,cow[i].t-1,res); 80 } 81 printf("%d",ans); 82 return 0; 83 } View Code

 

注意，最后修改时[l,r]的区间应在[l,r-1]上做改动，因为在r时刻，可理解为那群奶牛立即下车，有新的奶牛立即上车。

转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9746533.html

总结

以上是生活随笔为你收集整理的Luogu P1607 庙会班车【线段树】By cellur925的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。