当前位置：首页 > news >正文

中国计算机学会——2024年9月等级考试5级——第四题、森森快递(贪心+线段树)

news 2025/5/23 5:44:34

文章目录

- 题目
- 代码
- 线段树

题目

4、森森快递
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N-1)编号。由于道路限制，第i号城市（i=0, … , N-2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。
时间限制：5000
内存限制：262144
输入
输入在第一行给出两个正整数N和Q（2 ≤ N ≤ 105, 1 ≤ Q ≤ 105），表示总共的城市数以及订单数量。第二行给出(N-1)个数，顺次表示相邻两城市间的道路允许的最大运货重量Ci（i=0, … , N-2）。题目保证每个Ci是不超过231的非负整数。接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。
输出
在一行中输出可运输货物的最大重量。
样例输入
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>
#include <windows.h>
using namespace std;
struct Tree{//线段树，查询修改操作 log(n)int l,r,//左右边界v;//该道路区间各道路中最低承重，也是货运的最大量。bool operator<(const Tree &b)const{//小于运算符重载，定义了tree之间的排序规则 if(r==b.r)return l<b.l;return r<b.r;} 
}node[int(1e6+5)],//线段树各个节点1-9，最大到17<2*(n-1)route[int(1e5+1)];//各订单线路 
int n,//n个城市 road_v[int(1e5+1)],//0到n-1个城市间1到n-1条道路各自最大承重从 q,//q个订单s,t,//各订单货运始末城市 lazy[int(1e5+1)];//线段树懒消息，订单货运始末城市间各道路承重都要减去已找到的最低承重。二叉树遍历，非遍历 
long long int	ans;//最优解，最大货运重(每段道路运货量2^31,多个累计可能会2^31*10^5)
void build_tree(int x,int l,int r){//建立线段二叉树。参数(节点序号,左右边界)node[x].l=l,node[x].r=r;//先确定该区间的左右位置 if(l==r){node[x].v=road_v[l];return;}//递归基，确定线段最小单元(道路)的承重 int mid=l+r>>1;//该区间中间位置 build_tree(x<<1,l,mid);//递归建立x父节点的左区间 build_tree(x<<1|1,mid+1,r);//递归建立x父节点的右区间 node[x].v=min(node[x<<1].v,node[x<<1|1].v);/*递归递的过程一层层确认左右子节点一直到最小单元(城市间道路)，明确承重 归的过程再一层层从左右子节点找到最小值作为该父节点(区间)最大承重(各道路中最小承重) */
}
void view(string s,int v,int ans){//显示线段二叉树 cout<<s<<"\t本次可用承重"<<v<<"\t总货量"<<ans<<endl;queue<int> q1,q2;q1.push(1);//q1是当前层，q2是下层 int x,w=14;//(2*(n-1)-2*(n-1)%4)/4;while(!q1.empty()){//逐层输出所有节点 while(!q1.empty()){//输出当前层 x=q1.front();q1.pop();if(x>=2*(n-1))break;cout<<x<<"("<<node[x].l<<","<<node[x].r<<")="<<node[x].v;for(int i=0;i<w;i++)cout<<"\t"; q2.push(x<<1);q2.push(x<<1|1);//把已打印的节点的左右子节点放进队列2 }cout<<endl;w/=2;while(!q2.empty()){//拿出下一层 x=q2.front();if(x>=2*(n-1))break;q2.pop();q1.push(x);}}cout<<endl;
}
void do_lazy(int x){//处理懒信息。落实前面本来要减的该区间已占用承重。 if(lazy[x]==0)return;	//没有懒消息 node[x<<1].v-=lazy[x];	node[x<<1|1].v-=lazy[x];//从该区间所有道路减去已占用承重 lazy[x<<1]+=lazy[x];	lazy[x<<1|1]+=lazy[x];//下传懒信息 lazy[x]=0;//懒信息传下去了，完成使命了 
}
//参数(x节点，x节点区间，该线路区间) 
int find_amount(int x,int l,int r,int left,int right){//找到该区间各道路中最小承重 if(l>=left&&r<=right)return node[x].v;//找到该线路所在节点do_lazy(x);//搭顺风车，下行时刚好顺带处理懒信息(上次已采用最低承重，从相应区间所有道路承重中减去) int mid=l+r>>1,//中间 minv=2147483647;//2^31if(left<=mid)minv=min(minv,find_amount(x<<1,l,mid,left,right));//左区间找 if(mid<right)minv=min(minv,find_amount(x<<1|1,mid+1,r,left,right));//右区间找 return minv;
}
//参数(x节点，x节点区间，该线路区间，已占用承重) 
void reduce_amount(int x,int l,int r,int left,int right,int v){//从该区间各道路承重减去已占用承重 if(l>=left&&r<=right){//只要线路所在区间 node[x].v-=v;lazy[x]+=v;return;//减去已占用承重，并备到懒信息里，以备下次下行时继续减 }do_lazy(x);//搭顺风车，下行时刚好顺带处理懒信息(上次已采用最低承重，从相应区间所有道路承重中减去) int mid=l+r>>1;if(left<=mid)reduce_amount(x<<1,l,mid,left,right,v);//左区间 if(mid<right)reduce_amount(x<<1|1,mid+1,r,left,right,v);//右区间 node[x].v=min(node[x<<1].v,node[x<<1|1].v);
}
int main(){freopen("data.cpp","r",stdin);cin>>n>>q;for(int i=1;i<n;i++)cin>>road_v[i];//输入各城市间道路承重。0到1城市间是道路1 build_tree(1,1,n-1);//建立线段树 view("建树",0,0);//从顶往下建立线段二叉树 for(int i=0;i<q;i++){cin>>s>>t;if(s>t)swap(s,t);//输入并调整订单线路始末位置 route[i]=Tree{s+1,t};//各订单线路 }sort(route,route+q);//以终点城市为序升序排序，同则始发城市升序 //从左往右贪心找到最优解，肯定靠左订单线路的最高货量不影响最优解(全部线段最大货量) for(int i=0;i<q;i++){cout<<"区间\t"<<route[i].l<<":"<<route[i].r<<endl;int route_amount=find_amount(1,1,n-1,route[i].l,route[i].r);//找到该线路所在各道路中最低承重 ans+=route_amount;//贪心，左区间的最低承重，不影响整体最优解 reduce_amount(1,1,n-1,route[i].l,route[i].r,route_amount);//从该线路所在各道路减去已采用最低承重 view("减",route_amount,ans); }view("over",0,ans); cout<<ans;return 0;
}