luogu 3406 海底高铁 前缀和

题目链接

题意

给定一个数轴上的若干城市(1,2,3,...,n)，在第(i)到(i+1)((1leq ilt n))个城市间有铁路，通行方式可为
(1.)每次买票(花费(a*n));
(2.)买一张该段路线的卡，以后每次都用卡买票(花费(c+b*n, agt b));

现给出旅行路线，问最少的花费。

思路

旅行路线给定了，那么经过哪段路线多少次也就给定了。问题是数据范围(1e6)，怎么高效地得到经过哪段路线多少次呢？

前缀和思想。类似于树状数组区间修改单点求值的思想。

时间复杂度(O(n)).

Code

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
LL cnt[maxn];
int p[maxn];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) scanf("%d", &p[i]);
    for (int i = 1; i < m; ++i) {
        int l = p[i-1], r = p[i];
        if (l > r) swap(l, r);
        ++cnt[l], --cnt[r];
    }
    LL ans = 0;
    for (int i = 1; i < n; ++i) {
        cnt[i] += cnt[i-1];
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        int lim = c / (a - b);
        if (cnt[i] <= lim) ans += cnt[i] * a;
        else ans += c + cnt[i] * b;
    }
    printf("%lld
", ans);
    return 0;
}