首页 > 其他分享 >洛谷题单指南-前缀和差分与离散化-P3406 海底高铁

洛谷题单指南-前缀和差分与离散化-P3406 海底高铁

时间:2024-07-31 14:27:56浏览次数:15  
标签:前缀 P3406 int 洛谷题 差分 数组 每段

原题链接:https://www.luogu.com.cn/problem/P3406

题意解读:1-n个城市共了n段路,第i段路不买卡票价a[i],买卡票价b[i](卡本身花费c[i]),给定一个路程顺序,计算最少的通行费用。

解题思路:

根据路程,计算每段路各走了多少次,然后对于每段路,计算买卡和不买卡两种花费,取较小的累加即可。

如何计算每段路走了多少次?

1、朴素做法

枚举所有区间,再对区间内所有的路段,通过桶数组来标记走过的次数,时间复杂度n*m

2、差分

定义差分数组d[],对于每一个区间[l, r],执行d[l] += 1, d[r] -= 1,即可将该区间覆盖的所有路段都加1

然后,根据差分数组还原前缀和数组,即可枚举每段路走的次数,计算买卡和不买卡两种花费,取较小值累加。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int s[N]; //每一段路走了几次
int d[N]; //s的差分数组
int p[N]; //路径
int a[N], b[N], c[N];
int n, m;
long long ans;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> p[i];
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
    //对于每一段路程区间,用差分计算各段路走了多少次
    for(int i = 1; i < m; i++) 
    {
        int l = min(p[i], p[i + 1]);
        int r = max(p[i], p[i + 1]);
        d[l] += 1;
        d[r] -= 1;
    }
    //还原前缀和数组
    for(int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + d[i];
    }
    //对于每一段路,取花费最小的方式
    for(int i = 1; i <= n; i++)
    {
        ans += min(1ll * s[i] * a[i], 1ll * s[i] * b[i] + c[i]);
    }
    cout << ans;
    return 0;
}

 

标签:前缀,P3406,int,洛谷题,差分,数组,每段
From: https://www.cnblogs.com/jcwy/p/18334552

相关文章

  • 三种语言实现二维差分(C++/Python/Java)
    题目输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1,y1,x2,y2,c其中(x1,y1)和(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。请你将进行完所有操作后的矩阵输出。输入格式第一行包含整数n,......
  • 三种语言实现差分(C++/Python/Java)
    题目输入一个长度为n的整数序列。接下来输入m个操作,每个操作包含三个整数l,r,c表示将序列中[l,r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数n和m。第二行包含n个整数,表示整数序列。接下来m行,每行包含三个整数l,r,c,表......
  • lca总结+树上差分
    lcalca简称最近公共祖先——简介在此,不过多赘述这里主要写的是倍增算法,oi-wiki上用的是vector,由于本人不会,只会用链表,所以这里就放链表的代码了例题加一个数组按倍增数组的方式存距离即可题解——点击查看代码#include<bits/stdc++.h>#defineintlonglongconstint......
  • 洛谷题单指南-前缀和差分与离散化-P3017 [USACO11MAR] Brownie Slicing G
    原题链接:https://www.luogu.com.cn/problem/P3017题意解读:将一个r*c的矩阵,横向切成a条,每一条纵向切除b块,计算每一块子矩阵之和的最小值最大是多少。解题思路:要计算最小值中最大的,直觉上可以采用二分,下面来分析单调性:给定一个子矩阵块之和的值,值越小可以划分的条数、块数就越多......
  • 洛谷题单指南-前缀和差分与离散化-P2004 领地选择
    原题链接:https://www.luogu.com.cn/problem/P2004题意解读:在一个n*m的矩阵中,找到边长为c的正方形,使得正方形范围内的数之和最大,输出正方形的左上角坐标。解题思路:二维前缀和的简单应用第一步:计算二维前缀和第二步:枚举边长为c的正方形左上角,计算正方形区域的数之和,更新答案第......
  • 洛谷题单指南-前缀和差分与离散化-P1884 [USACO12FEB] Overplanting S
    原题链接:https://www.luogu.com.cn/problem/P1884题意解读:给定n个矩形的平面直角坐标系下左上角、右下角的坐标,计算这n个矩形能覆盖的的格子数。解题思路:直观上来看,此题是一个差分应用,针对二维差分数组,将n个矩形区域内每个格子的值加1,然后统计有多少个不为0的格子即可。但是!坐......
  • 洛谷题单指南-前缀和差分与离散化-P1496 火烧赤壁
    原题链接:https://www.luogu.com.cn/problem/P1496题意解读:给定n个区间[a,b),计算所有区间覆盖的总长度。解题思路:方法1、离散化先思考一种比较直观的思路:既然要计算多个区间覆盖的总长度,可以枚举每一个区间[a,b),通过一个桶数组来标记区间中所有的点f[x]=1,最终统计所有为1的......
  • 前缀和与差分
    前缀和与差分前缀和定义:前缀和可以简单理解为「数列的前n项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。一维前缀和模板for(inti=1;i<=n;i++)sum[i]=sum[i-1]+a[i];时间复杂度:O(n)原理数组sum用于储存前i个元素的和,数组a......
  • 差分约束
    差分约束差分约束是一种特殊的n元一次不等式组,m个约束条件,可以组成形如下的格式:\[\begin{cases}x_1-x_1^{'}\ley_1\\x_2-x_2^{'}\ley_2\\\cdots\\x_m-x_m^{'}\ley_m\end{cases}\]我们的任务是需要求出一组解,\(x_1=a_1,x_2=a_2,\cdots,x_n=a_n\)使得不等式......
  • 表面贴装差分输出晶体振荡器 DSO533SK/DSO533SJ 全面解析
    表面贴装差分输出晶体振荡器DSO533SK/DSO533SJ全面解析摘要:本文深入探讨表面贴装差分输出晶体振荡器DSO533SK/DSO533SJ的特性、工作原理、优势、应用领域以及使用中的关键要点。通过详细的阐述和实例分析,为读者提供全面且深入的技术解读。一、引言在当今高度集成和高......