小树311_森林小道

小树311_森林小道原题链接森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N−1)编号。由于道路限制,第i号城市(i=0,⋯,N−2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过C​i​​ 公斤。公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从S​j​​ 号城市运输到T​j​​ 号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N−1)编号。由于道路限制,第i号城市(i=0,⋯,N−2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过C
​i
​​ 公斤。

公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从S
​j
​​ 号城市运输到T
​j
​​ 号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。

为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。

输入格式:
输入在第一行给出两个正整数N和Q(2≤N≤10
​5
​​ , 1≤Q≤10
​5
​​ ),表示总共的城市数以及订单数量。

第二行给出(N−1)个数,顺次表示相邻两城市间的道路允许的最大运货重量C
​i
​​ (i=0,⋯,N−2)。题目保证每个C
​i
​​ 是不超过2
​31
​​ 的非负整数。

接下来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>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 1e9;
struct { 

int l,r;
ll v;
ll add;
}tr[4 * N];
ll a[N];
vector<PII>p;
void push_up(int u){ 

tr[u].v = min(tr[left(u)].v + tr[left(u)].add,tr[right(u)].v + tr[right(u)].add);
}
void push_down(int u){ 

if(tr[u].add){ 

tr[u].v += tr[u].add;
tr[left(u)].add += tr[u].add;
tr[right(u)].add += tr[u].add;
tr[u].add = 0;
}
}
void build(int l,int r,int u){ 

if(l == r)tr[u] = { 
l,r,a[l],0};
else{ 

tr[u] = { 
l,r,0,0};
int mid = (l + r) >> 1;
build(l,mid,left(u));
build(mid + 1,r,right(u));
push_up(u);
}
}
void modify(int l,int r,ll x,int u){ 

if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;
else { 

push_down(u);   //修改的时候也必须push_down
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid)modify(l,r,x,left(u));
if(r > mid)modify(l,r,x,right(u));
push_up(u);
}
}
ll query(int l,int r,int u){ 

if(tr[u].l >= l && tr[u].r <= r)return tr[u].v + tr[u].add;
else{ 

push_down(u);
ll v = LINF;
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid)v = query(l,r,left(u));
if(r > mid)v = min(v,query(l,r,right(u)));
push_up(u);
return v;
}
}
bool cmp(const PII &a,const PII &b){ 

if(a.y != b.y)return a.y < b.y;
else return a.x < b.x;
}
int main(){ 

int n,m,x,y;
cin>>n>>m;
for(int i = 0;i < n - 1;i ++)cin>>a[i];
build(0,n - 2,1);
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
if(x > y)swap(x,y);
p.push_back({ 
x,y});
}
sort(p.begin(),p.end(),cmp);        //贪心
ll res = 0;
for(int i = 0;i < p.size();i ++){ 

ll m = query(p[i].x,p[i].y - 1,1);
modify(p[i].x,p[i].y - 1,-m,1);
res += m;
}
printf("%lld\n",res);
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169023.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux安装weget命令,linux安装wget命令

    linux安装weget命令,linux安装wget命令wget命令是linux系统下的一个常用命令。下面由学习啦小编为大家整理了linux安装wget命令的相关知识,希望大家喜欢!linux安装wget命令方法一debian或者ubuntu:sudoapt-getinstallwgetcentos:sudoyum-yinstallwgetlinux安装wget命令方法二我们先安装linux系统比如centos7.1里面有的就…

    2022年10月16日
  • Page.RegisterStartupScript的使用方法

    Page.RegisterStartupScript的使用方法用于后台输出Javascript执行段打开一个新窗口:Page.RegisterStartupScript(“starup”,”<scriptlanguage=’javascript’>window.open(‘”+url+”‘,”,’toolbar=no,resizable=yes,scrollbars=yes’)</script>”)警告…

  • 光纤交换机划分zone方法

    光纤交换机划分zone方法以是"wwn",还可以是zone的别名和QuickloopAL_PAs。交换机默认域为1,端口号从0-15。可以用switchshow来查看配置。重要的是记住必须用cfgsave保存,和cfgenable让其生效。  ***********************************************************在IBM2109光纤通道交换机上设置分区的步骤 环境 SAN2109如何在IBM2109光纤通道交换机上设置分区(Zoning)在存

  • 高斯滤波原理及应用_数字图像处理高斯滤波器

    高斯滤波原理及应用_数字图像处理高斯滤波器1一维高斯分布 1.1一维高斯分布的定义 若连续型随机变量X的概率密度为:其中,为常数,则称X服从参数为,的正态分布或高斯分布,记为 1.2一维高斯分布的曲线 横轴表示可能的取值x,竖轴表示概率分布密度F(x),那么不难理解这样一个曲线与x轴围…

    2022年10月22日
  • jQuery+CSS3文字跑马灯特效

    jQuery+CSS3文字跑马灯特效是一款将跑马灯背景制作为3D立方体效果,文字在上面移动时,就像是文字投影到墙壁上,在转角出会改变运动方向。效果展示 http://hovertree.co

    2021年12月27日
  • linux ftp lcd 命令,Linux FTP命令使用实例「建议收藏」

    linux ftp lcd 命令,Linux FTP命令使用实例「建议收藏」之前我们说过linuxscp的命令,是用来两台Linux服务器之前传输数据的。那么我们如何在Linux服务器与没有SSH的虚拟主机传输数据呢,我们可以使用Linux的FTP命令来实现,下面是一些使用实例。ftpwww.centos.bz这个命令表示试图连接www.centos.bz的FTP服务器,如果成功连接上,就会要求输入FTP用户名和密码。ftp>help连接上FTP服务器后,键入…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号