森森快递的最优运输策略

《动物森友会》中的岛民互动也有策略策略 #生活乐趣# #游戏乐趣# #策略游戏#

森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的NNN个城市，这些城市从左到右依次从0到(N−1)(N-1)(N−1)编号。由于道路限制，第iii号城市（i=0,⋯,N−2i=0, \cdots , N-2i=0,⋯,N−2）与第(i+1)(i+1)(i+1)号城市中间往返的运输货物重量在同一时刻不能超过CiC_iC​i​​公斤。
公司开张后很快接到了QQQ张订单，其中jjj张订单描述了某些指定的货物要从SjS_jS​j​​号城市运输到TjT_jT​j​​号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。输入格式：输入在第一行给出两个正整数NNN和QQQ（2≤N≤1052 \le N \le 10^52≤N≤10​5​​, 1≤Q≤1051 \le Q \le 10^51≤Q≤10​5​​），表示总共的城市数以及订单数量。第二行给出(N−1)(N-1)(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量CiC_iC​i​​（i=0,⋯,N−2i=0, \cdots , N-2i=0,⋯,N−2）。
题目保证每个CiC_iC​i​​是不超过2312^{31}2​31​​的非负整数。接下来QQQ行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。输出格式：在一行中输出可运输货物的最大重量。
输入样例：
10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2
输出样例：
7
样例提示：我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。

参考大神的做法
线段树加贪心，求每段区间的最小值相加就好了
怎么去理解呢，就是你把每一段区间的最小下值都加在了一起，那么和不就是总的最大和？贪心就是去处理这个步骤

#include<bits/stdc++.h> using namespace std; #define N 200005 int f[N]; long long Min[2*N+1],lazy[2*N+1]; void pushdown(int rt){ if(!lazy[rt]) return ; lazy[rt*2]+=lazy[rt],lazy[rt*2+1]+=lazy[rt]; Min[rt*2]-=lazy[rt],Min[rt*2+1]-=lazy[rt]; lazy[rt]=0; return ; } void build(int l,int r,int rt){ if(l==r) { Min[rt]=f[l]; return; } int mid =(l+r)/2; build(l,mid,rt*2); build(mid+1,r,rt*2+1); Min[rt]=min(Min[rt*2],Min[rt*2+1]); return ; } long long qmin(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r)return Min[rt]; pushdown(rt); int mid=(l+r)/2; long long sum=1e18; if(L<=mid) sum=min(sum,qmin(L,R,l,mid,rt*2)); if(R>mid) sum=min(sum,qmin(L,R,mid+1,r,rt*2+1)); return sum; } void Update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&R>=r){ lazy[rt]+=c,Min[rt]-=c; return ; } int mid=(l+r)/2; if(L<=mid) Update(L,R,c,l,mid,rt*2); if(R>mid) Update(L,R,c,mid+1,r,rt*2+1); Min[rt]=min(Min[rt*2],Min[rt*2+1]); return ; } int main() { int n,m; cin>>n>>m; for(int i=1;i<n;i++) cin>>f[i]; build(1,n-1,1); pair<int,int>p[N]; for(int i=0,l,r;i<m;i++){ cin>>l>>r; if(l>r) swap(l,r); p[i]={r,l}; } sort(p,p+m); long long sum=0; for(int i=0;i<m;i++){ int num=qmin(p[i].second+1,p[i].first,1,n-1,1); sum+=num; Update(p[i].second+1,p[i].first,num,1,n-1,1); } cout<<sum; return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

网址：森森快递的最优运输策略 https://www.yuejiaxmz.com/news/view/568948

相关内容

小森生活赚钱怎么最快 小森生活金币速刷攻略
森马电商2020校园招聘简章
森森之家软件下载
帕金森病患者生活质量提升策略
小森生活生活技能攻略 技能怎么升级
交通运输节能策略
小森生活基础攻略
动物森林 动物之森：快乐家园设计师
小森生活攻略大全 小森生活新手所有攻略汇总
小森生活—养狗攻略（萌新必备）

随便看看