首页 > 编程语言 >P3406 海底高铁(C++)

P3406 海底高铁(C++)

时间:2024-05-27 11:03:41浏览次数:31  
标签:10 30 P3406 int 城市 高铁 cin C++ 100

海底高铁

题目描述

该铁路经过 N N N 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 i i i 段铁路连接了城市 i i i 和城市 i + 1 ( 1 ≤ i < N ) i+1(1\leq i<N) i+1(1≤i<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 N−1 行,表示第 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 N≤1000,M≤1000。

对于 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,N≤105,Ai​,Bi​,Ci​≤105。

思路

本题其实就是一道简单的前缀和的问题,正常用前缀和做就ok了。

代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], a[N], b[N], c[N];
long long s, ans[N];
int n, m, i;
int main() {
   cin >> n >> m;
   for (i = 1; i <= m; i++)
   	cin >> p[i];
   for (i = 1; i < n; i++)
   	cin >> a[i] >> b[i] >> c[i];

   for (i = 1; i <= m - 1; i++) {
   	ans[min(p[i], p[i + 1])]++;
   	ans[max(p[i], p[i + 1])]--;
   }
   for (i = 1; i <= n; i++) ans[i] += ans[i - 1];
   for (i = 1; i < n; i++) s += min(a[i] * ans[i], (b[i] * ans[i] + c[i]));

   cout << s << endl;
}

整活代码

#include<iostream>
#define f(_,x)for(int _=1;_<x;_++)
using namespace std;
const int N=1e5+10;
long long p[N],a[N],b[N],c[N],n,m,s,d[N];
int main(){cin>>n>>m;f(i,m+1)cin>>p[i];f(i,n)cin>>a[i]>>b[i]>>c[i];
f(i,m)d[min(p[i],p[i+1])]++,d[max(p[i],p[i+1])]--;f(i,n+1)d[i]+=d[i-1];
f(i,n)s+=min(a[i]*d[i],b[i]*d[i]+c[i]);cout<<s;}

标签:10,30,P3406,int,城市,高铁,cin,C++,100
From: https://blog.csdn.net/chq66666/article/details/139198722

相关文章

  • n-皇后问题(c++)
    ......
  • C/C++ 指针注意事项
    C/C++中的指针是强大的工具,但需要谨慎使用,错误的使用可能会导致程序崩溃或者内存泄漏。以下指针相关注意事项:初始化指针:在使用指针之前,一定要初始化它,否则它将指向一个随机的内存地址,这可能导致程序崩溃。未初始化的指针通常被称为“野指针”。避免空指针解引用:在解引用......
  • Qt/C++音视频开发75-获取本地有哪些摄像头名称/Qt内置函数方式
    一、前言在需要打开本地摄像头的场景中,有个需求绕不开,那就是如何获取本地有哪些摄像头设备名称,这样可以提供下拉框给用户选择,不然你让用户去填设备名,你觉得用户会知道是啥,他会操作吗?就算你提供了详细的查看步骤,估计也很难,如果用户是程序员还好,如果是电脑小白,鼠标都用不好,你还让他......
  • C++技能进阶指南——多态语法剖析
            前言:多态是面向对象的三大特性之一。顾名思义,多态就是多种状态。那么是什么的多种状态呢?这里的可能有很多。比如我们去买火车票,有普通票,学生票;又比如我们去旅游,有儿童票,有成人票等等。这些都是多态的例子。具体转化为我们的编程思想就是:让不同类型......
  • C++干货 --类和对象(二)
    前言:     上文中,我们介绍了类这一重要知识点,包括为什么要有类、类的使用方法、封装、以及对象实例化。详情可以去看我的文章:写文章-CSDN创作中心C++干货--类和对象(一)-CSDN博客写文章-CSDN创作中心这篇文章,我们简单分析一下默认成员函数这一重要知识点。默认成员......
  • c++类型转换
    强类型语言强类型语言也称为强类型定义语言,是一种总是强制类型定义的语言。它的主要特点包括:强制类型定义:强类型语言要求变量在使用之前必须明确声明其类型,并且限制了不同类型之间的隐式转换。这意味着所有变量都必须先定义后使用,并且变量的类型在编译时就被严格检查。编......
  • 算法刷题笔记 前缀和(C++实现)
    文章目录题目描述基本思路实现代码题目描述输入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l,r。对于每个询问,输出原序列中从第l个数到第r个数的和。输入格式第一行包含两个整数n和m。第二行包含n个整数,表示整数数列。接下来m行,每行包含两个整数......
  • 算法刷题笔记 数的范围(C++实现)(二分法重要例题)
    文章目录题目描述题目思路题目代码(C++)题目感想题目描述给定一个按照升序排列的长度为n的整数数组,以及q个查询。对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。如果数组中不存在该元素,则返回-1-1。输入格式:第一行包含整数n和q,表示数组长度和询......
  • 【C++风云录】走进数字农业:农业科学与粮食安全
    跨越边界:农业模拟库的编程特性与应用领域前言在本篇文章中,我们将深入探讨六个领域的软件库—APSIM,AgroLib,CropModelMKS,SoilR,Bionet和FSEarth。这些库均用于农业生态系统建模、作物模拟、农业数据处理和分析、合成作物模型构造、土壤碳氮循环模型集成、生物网络模拟以及农......
  • 【C++】牛客 ——DP36 abb
    ✨题目链接:DP36abb✨题目描述 leafee最近爱上了abb型语句,比如“叠词词”、“恶心心”leafee拿到了一个只含有小写字母的字符串,她想知道有多少个"abb"型的子序列?定义:abb型字符串满足以下条件:字符串长度为3。字符串后两位相同。字符串前两位不同。✨输入......