森森快递 天梯

本文主要是介绍森森快递 天梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对每个快递任务 如果完全包含其他任务 那就舍弃这个任务 因为这种任务又臭又长 占用的资源多 其收益完全可以被其完全包含的任务代替 所以对任务去重之后只剩下两两不包含的任务区间
若两个任务区间不相交 那就都执行 若是相交的话 两者先后执行顺寻是无所谓的 所以找出区间最小值 再在整个区间上减去即可

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=0x3f3f3f3f3f3f3f3f;
const ll maxn=1e5+10;struct node
{ll l,r;
};node seg[maxn];
ll minn[4*maxn],laz[4*maxn];
ll n,q;bool cmp(node n1,node n2)
{if(n1.l==n2.l) return n1.r>n2.r;else return n1.l<n2.l;
}void pushup(ll cur)
{minn[cur]=min(minn[2*cur],minn[2*cur+1]);
}void pushdown(ll cur)
{if(laz[cur]!=0){minn[2*cur]+=laz[cur];laz[2*cur]+=laz[cur];minn[2*cur+1]+=laz[cur];laz[2*cur+1]+=laz[cur];laz[cur]=0;}
}void build(ll l,ll r,ll cur)
{ll m;if(l==r){scanf("%lld",&minn[cur]);return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}ll query(ll pl,ll pr,ll l,ll r,ll cur)
{ll res;ll m;if(pl<=l&&r<=pr){return minn[cur];}pushdown(cur);res=N,m=(l+r)/2;if(pl<=m) res=min(res,query(pl,pr,l,m,2*cur));if(pr>m) res=min(res,query(pl,pr,m+1,r,2*cur+1));pushup(cur);return res;
}void update(ll pl,ll pr,ll val,ll l,ll r,ll cur)
{ll m;if(pl<=l&&r<=pr){minn[cur]+=val;laz[cur]+=val;return;}pushdown(cur);m=(l+r)/2;if(pl<=m) update(pl,pr,val,l,m,2*cur);if(pr>m) update(pl,pr,val,m+1,r,2*cur+1);pushup(cur);
}int main()
{ll ans,res;ll i,gou;scanf("%lld%lld",&n,&q);build(1,n-1,1);for(i=1;i<=q;i++){scanf("%lld%lld",&seg[i].l,&seg[i].r);if(seg[i].l>seg[i].r) swap(seg[i].l,seg[i].r);seg[i].l++;}sort(seg+1,seg+q+1,cmp);ans=0,gou=N;for(i=q;i>=1;i--){if(seg[i].r<gou){res=query(seg[i].l,seg[i].r,1,n-1,1);update(seg[i].l,seg[i].r,-res,1,n-1,1);ans+=res;}gou=min(gou,seg[i].r);}printf("%lld\n",ans);return 0;
}

 

这篇关于森森快递 天梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---