题解 P1607 【[USACO09FEB]庙会班车Fair Shuttle】

Starria的脑残粉

2017-10-29 20:56:46

Solution

想刷一下线段树题然后就写了个线段树。。 排序后贪心思路是显然正确的因为找不出更优解。。 线段树维护区间加区间max 连标记下传都不用,直接永久化好了 可以说很傻了 贴代码: ```cpp #include<bits/stdc++.h> using namespace std; int k,n,c,ans,ma[1000000],lazy[1000000]; struct lsg{int x,y,z;}a[1000000]; int read(){ char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar(); int kk=1,k=0;if (c=='-')kk=-1,c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k; }int findit(int x,int y,int l,int r,int d){//查询max操作 if (x<=l&&y>=r)return ma[d]; int m=(l+r)/2,ans=lazy[d]; if (x<=m)ans=max(ans,findit(x,y,l,m,d*2)+lazy[d]); if (y>m)ans=max(ans,findit(x,y,m+1,r,d*2+1)+lazy[d]); return ans; }void putit(int x,int y,int z,int l,int r,int d){//区间加 if (x<=l&&y>=r){lazy[d]+=z;ma[d]+=z;return;} int m=(l+r)/2;if (x<=m)putit(x,y,z,l,m,d*2); if (y>m)putit(x,y,z,m+1,r,d*2+1); ma[d]=max(ma[d*2],ma[d*2+1])+lazy[d]; }bool pd(lsg x,lsg y){return x.y<y.y;}//按右端点排序 int main(){ k=read();n=read();c=read();for (int i=1;i<=k;i++)a[i].x=read(),a[i].y=read()-1,a[i].z=read(); sort(a+1,a+1+k,pd);for (int i=1;i<=k;i++){ int x=findit(a[i].x,a[i].y,1,n,1),y=min(c-x,a[i].z);//贪心 ans+=y;putit(a[i].x,a[i].y,y,1,n,1); }cout<<ans<<endl; } ```