題目傳送門

據(jù)說(shuō)可以用貪心做？算了算了...我都不會(huì)貪...。

---

?

開(kāi)始想的是用線段樹(shù)，先建出一顆空樹(shù)，然后輸進(jìn)區(qū)間操作后就維護(hù)最大值，顯然開(kāi)始我忽視了班車的容量以及可以有多組奶牛坐在一起的信息。

我們肯定想要有更多的區(qū)間被選中，根據(jù)線段覆蓋問(wèn)題的套路，我們要優(yōu)先選結(jié)束位置最小的，能選就選，但是需要判斷下能不能選，就是比較下當(dāng)前區(qū)間最大值和容量的關(guān)系，盡量加上，進(jìn)行修改。說(shuō)白了就是在維護(hù)帶修改的區(qū)間最大值。

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

?

注意，最后修改時(shí)[l,r]的區(qū)間應(yīng)在[l,r-1]上做改動(dòng)，因?yàn)樵趓時(shí)刻，可理解為那群奶牛立即下車，有新的奶牛立即上車。

轉(zhuǎn)載于:https://www.cnblogs.com/nopartyfoucaodong/p/9746533.html

總結(jié)

以上是生活随笔為你收集整理的Luogu P1607 庙会班车【线段树】By cellur925的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。