(洛谷P34060):海底高铁—->差分数组,贪心思想

海底高铁

题目描述

该铁路经过 N N N 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 i i i 段铁路连接了城市 i i i 和城市 i + 1 ( 1 ≤ i < N ) i+1(1\leq i<N) i+1(1i<N)。如果搭乘的比较远,需要购买多张车票。第 i i i 段铁路购买纸质单程票需要 A i A_i Ai 博艾元。

虽然一些事情没有协调好,各段铁路公司也为了方便乘客,推出了 IC 卡。对于第 i i i 段铁路,需要花 C i C_i Ci 博艾元的工本费购买一张 IC 卡,然后乘坐这段铁路一次就只要扣 B i ( B i < A i ) B_i(B_i<A_i) Bi(Bi<Ai) 元。IC 卡可以提前购买,有钱就可以从网上买得到,而不需要亲自去对应的城市购买。工本费不能退,也不能购买车票。每张卡都可以充值任意数额。对于第 i i i 段铁路的 IC 卡,无法乘坐别的铁路的车。

Uim 现在需要出差,要去 M M M 个城市,从城市 P 1 P_1 P1 出发分别按照 P 1 , P 2 , P 3 , ⋯   , P M P_1,P_2,P_3,\cdots,P_M P1,P2,P3,,PM 的顺序访问各个城市,可能会多次访问一个城市,且相邻访问的城市位置不一定相邻,而且不会是同一个城市。

现在他希望知道,出差结束后,至少会花掉多少的钱,包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数, N , M N,M N,M

接下来一行, M M M 个数字,表示 P i P_i Pi

接下来 N − 1 N-1 N1 行,表示第 i i i 段铁路的 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci

输出格式

一个整数,表示最少花费

样例 #1

样例输入 #1

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

样例输出 #1

6394

提示

2 2 2 3 3 3 以及 8 8 8 9 9 9 买票,其余买卡。

对于 30 % 30\% 30% 数据 M = 2 M=2 M=2

对于另外 30 % 30\% 30% 数据 N ≤ 1000 , M ≤ 1000 N\leq1000,M\leq1000 N1000M1000

对于 100 % 100\% 100% 的数据 M , N ≤ 1 0 5 , A i , B i , C i ≤ 1 0 5 M,N\leq 10^5,A_i,B_i,C_i\le10^5 M,N105Ai,Bi,Ci105

##主要思想:
明确每段区间(城市i->i+1)经过次数。
举例:1->3,经过城市车站123;1->4,经过城市1234,包含了1->3;1->5,经过城市12345,包含1->3;那么从1->3可以不用办理三次工本费,办理一次即可;而不管是哪段城市都要付车票,要么纸质车票要么充值IC卡,只是工本费并不是每个区间都需要付,这是问题的核心。
在这里插入图片描述
在这里插入图片描述

下面展示一些 内联代码片

// An highlighted block
var foo = 'bar';

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long a[maxn],b[maxn],c[maxn];
int route[maxn],passnum[maxn];
//这里没有创建差分数组,由于passnum初始均为0,passnum既做原数组又做差分数组
//route表示路径中经过的车站(1->M-1),passnum[i]表示从i->i+1经过的次数,即最终数组
int main()
{
    //第一步:输入
    int N,M;cin>>N>>M;//N个城市,M个访问
    for(int i=1;i<=M;++i)
        cin>>route[i];//举例3 1 4 1 5 9 2 6 5 3
    
    for(int i=1;i<=N-1;++i)//9个城市,9-1段
        cin>>a[i]>>b[i]>>c[i];//举例200 100 50
    
    //第二步:利用差分数组对经过的区间车站(i->i+1)的经过次数加1
    for(int i=1;i<=M-1;++i)//思考这里为什么是M-1
    {
        passnum[min(route[i],route[i+1])]+=1;
        passnum[max(route[i],route[i+1])]-=1;
    }
    
    //第三步:对差分数组求前缀和得到最终数组
    //原数组passnum[maxn]最开始全为0,经过差分求前缀和得到新的原数组
    for(int i=1;i<=N-1;++i)//思考这里为什么是N-1? i=8时 表示城市8->城市9
    {
        passnum[i]=passnum[i-1]+passnum[i];
    }
    
    //第四步:遍历最终表示经过次数的数组
    //for(int i=1;i<=N-1;++i)
    //    cout<<passnum[i];
    
    //第五步:比较某段区间哪种方案更实惠 注意答案也应该为longlong
    //纸质票价*某段区间经过次数---IC卡票价*某段区间经过次数+一次工本费
    //贪心思维:每次都选择最优惠的方案 得到的最终答案即最少花费
    long long answer=0;
    for(int i=1;i<=N-1;++i)
    {
        answer+=min(a[i]*passnum[i],b[i]*passnum[i]+c[i]);
    }
    cout<<answer;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/536812.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Web】CTFSHOW-ThinkPHP5-6反序列化刷题记录(全)

目录 web611 web612 web613-622 web623 web624-626 纯记录exp&#xff0c;链子不作赘述 web611 具体分析&#xff1a; ThinkPHP-Vuln/ThinkPHP5/ThinkPHP5.1.X反序列化利用链.md at master Mochazz/ThinkPHP-Vuln GitHub 题目直接给了反序列化入口 exp: <?ph…

实验9 内置对象application

一、实验目的 掌握怎样在JSP中使用内置对象application 二、实验项目内容&#xff08;实验题目&#xff09; 编写代码&#xff0c;掌握application的用法。【参考课本例题4-16 留言板 】 三、源代码以及执行结果截图&#xff1a; example4_16.jsp <% page language"…

【2024年认证杯】A题详细思路+数据(来源)+成品论文+模型代码

2024年认证杯A题 解题思路 ⭐⭐第一问题分析第二问题分析第三问题分析 数据与数据来源指标解释数据来源 参考论文python/ matlab 代码 解题思路 ⭐⭐ 这个题目要求我们围绕人造保暖纤维的保暖能力进行建模&#xff0c;并解决三个具体问题。 第一问题分析 第一问题要求建立一…

【C 数据结构】循环链表

文章目录 【 1. 基本原理 】【 2. 循环链表的创建 】2.1 循环链表结点设计2.2 循环单链表初始化 【 3. 循环链表的 插入 】【 4. 循环单链表的 删除操作 】【 5. 循环单链表的遍历 】【 6. 实例 - 循环链表的 增删查改 】【 7. 双向循环链表 】 【 1. 基本原理 】 对于单链表以…

【嵌入式学习】ARM day04.11

一、思维导图 二、练习 实现三个灯闪烁 汇编代码 .text .global _start _start: 使能GPIOE和F时钟LDR r0,0x50000A28LDR r1,[R0]ORR R1,R1,#(0X3<<4)STR R1,[R0]配置GPIOE和F的MODER寄存器LDR r0,0x50006000 GPIOELDR R1,0X50007000 G…

C语言.指针(5)

指针&#xff08;5&#xff09; 1.sizeof和strlen的对比1.1sizeof1.2strlen1.3sizeof和strlen的对比 2.数组和指针笔试题解析2.1一维数组2.2字符数组2.3二维数组 3.指针运算笔试题解析3.1 题目13.2 题目23.3 题目33.4 题目43.5 题目53.6 题目63.7 题目7 1.sizeof和strlen的对比…

Qt栅格布局的示例

QGridLayout * layoutnew QGridLayout;for(int i0;i<10;i){for(int j0;j<6;j){QLabel *labelnew QLabel(this);label->setText(QString("%1行%2列").arg(i).arg(j));layout->addWidget(label,i,j);}}ui->widget->setLayout(layout); 这样写程序会崩…

NC65 查询默认密码(sql)

NC65 使用sql查询设置的默认密码&#xff08;如果系统设置有&#xff09;&#xff1a; select * from sm_user_defaultpwd

电商技术揭秘十三:云计算在电商中的应用场景

相关系列文章 电商技术揭秘一&#xff1a;电商架构设计与核心技术 电商技术揭秘二&#xff1a;电商平台推荐系统的实现与优化 电商技术揭秘三&#xff1a;电商平台的支付与结算系统 电商技术揭秘四&#xff1a;电商平台的物流管理系统 电商技术揭秘五&#xff1a;电商平台…

C++11 设计模式2. 简单工厂模式

简单工厂&#xff08;Simple Factory&#xff09;模式 我们从实际例子出发&#xff0c;来看在什么情况下&#xff0c;应用简单工厂模式。 还是以一个游戏举例 //策划&#xff1a;亡灵类怪物&#xff0c;元素类怪物&#xff0c;机械类怪物&#xff1a;都有生命值&#xff0…

「Java开发指南」如何利用MyEclipse启用Spring DSL?(一)

本教程将引导您通过启用Spring DSL和使用Service Spring DSL抽象来引导Spring和Spring代码生成项目&#xff0c;本教程中学习的技能也可以很容易地应用于其他抽象。在本教程中&#xff0c;您将学习如何&#xff1a; 为Spring DSL初始化一个项目创建一个模型包创建一个服务和操…

实体抽取全解析:技术与实战

目录 一、前言二、实体抽取技术概览基于规则的实体抽取基于统计的实体抽取基于深度学习的实体抽取 三、实体抽取的发展历程早期的实体抽取方法基于规则和词典的方法基于特征的机器学习方法 深度学习时代的实体抽取从传统模型到神经网络序列标注模型的兴起预训练语言模型的革命 …

如何修改 MySQL 8.0 的密码

在 MySQL 8.0 中修改用户密码是数据库管理的一项基本任务。本教程将引导您完成这一过程&#xff0c;确保即使是初学者也能理解并成功执行。 介绍 MySQL 是最流行的关系数据库管理系统之一。作为数据库管理员或开发人员&#xff0c;您可能需要更改用户的密码来保证账户安全。本…

QT 信号与槽的简单使用

文章目录 1.通过Singloat and Slots Editor 添加信号与槽2. 通过拖动动态添加3.通过转到槽方式添加&#xff08;自动关联&#xff09;4. 自定义信号与槽&#xff08;connect)4.1 connect方式4.2 自定义信号 1.通过Singloat and Slots Editor 添加信号与槽 点添加&#xff0c;然…

突破像素限制,尽显照片细腻之美——Topaz Gigapixel AI for Mac/Win

在这个数字化的时代&#xff0c;我们都热爱用照片记录生活中的美好瞬间。然而&#xff0c;有时候我们会发现&#xff0c;由于各种原因&#xff0c;照片的像素可能无法满足我们的需求。这时候&#xff0c;Topaz Gigapixel AI for Mac/Win 这款强大的照片放大工具应运而生。 Top…

open c UF_MODL_create_simple_hole 识别放置平面 UF_MODL_ask_face_data

在BLOCK上创建一个简单孔 UF_FEATURE_SIGN sign UF_NULLSIGN;double block_orig[3] { -25.0,-25.0,0.0 };char* block_len[3] { "50","50","30" };tag_t blk_obj;UF_MODL_create_block1(sign, block_orig, block_len, &blk_obj);tag_t bo…

PSPICE、Multisim和Saber哪个更适合电路仿真?没想到是它

PSPICE、Multisim和Saber这三个软件都是非常流行的模拟电路仿真工具&#xff0c;它们各自有各自的优缺点&#xff0c;我简单讲一下&#xff1a; PSPICE&#xff1a; 优点&#xff1a; 精度高&#xff1a;PSPICE是专业的电路仿真软件&#xff0c;可以进行高精度的模拟电路仿真…

兮兮牧场养殖小游戏积分兑换互动商城引流模式

刚注册的新会员必须要进入牧场才能激活所有功能 一、获得动物的途径的方式 第一种是邀请好友注册获得&#xff0c;第二种是看广告获得 邀诘好友注册获得动物明细: 1、从兮兮牧场的邀请好友的链接去邀请好友才能获得&#xff0c;其他邀请码无效 2、注册赠送小鸡一只; 3、邀…

基于Springboot + vue + MySQL +Tomcat 社区医院管理服务系统 (含源码)

目录 &#x1f4da; 前言 &#x1f4d1;摘要 &#x1f4d1;系统架构 &#x1f4da; 数据库设计 &#x1f4ac; 用户注册实体属性图 &#x1f4ac; 医生实体属性图 &#x1f4da; 系统功能的具体实现 &#x1f4ac; 前台模块 用户注册 医生信息 &#x1f4ac; 后台功能模…

Docker部署SpringBoot+Vue前后端分离项目

文章目录 1. 安装Docker1. 1 卸载旧版Docker1.2 配置yum仓库1.3 安装Docker1.4 添加自启动配置1.5 配置阿里云镜像加速1.6 测试 2. 安装Nginx2.1 拉取镜像2.2 安装Nginx2.3 测试 3. 安装MySQL3.1 拉取镜像3.2 安装MySQL3.3 连接MySQL 4. 部署SpringBoot项目4.1 Maven打包4.2 编…