原题背景

可以直接跳到核心

原题链接

分析

可以贪心，选择买卡还是不买卡的关键在于这段铁路会被访问多少次

1

s[i].money = min(s[i].a*s[i].vis, s[i].c+s[i].b*s[i].vis)

核心

如何统计这段铁路会被访问多少次呢？(注意左闭右开原则)

给出多组i 与 j

要让 i 到 j 的每个数组中的成员 vis+1

例如： s[i].vis+1,s[i+1].vis+1,…,s[j].vis+1

如果暴力 for 循环对每段赋值的话是会超时的。

1
2
3

for (int i = from; i < to; ++i) {
    s[i].vis++;
}

线段树或者树状数组或许可以完成，但没必要

解决方法

我们在开始的位置+1，并在结尾的位置-1。最后再求前缀和，得到的就是每段的访问次数了。

例如

从车站 1 -> 5 和 1 -> 4。 (下方表示第 i 段铁路，到达站点五，并不会经过第 5 段铁路)

应该出现的结果是:

按照我们的方法:

对这个数组求前缀和:

如此，我们只需要循环一遍就能够完成对区间访问次数的计数了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 多次调用，处理每个区间头尾
void addVis(int a, int b)
{
    if (a > b) {
        swap(a, b);
    }
    stations[a].vis++;
    stations[b].vis--;
}

void solve()
{
    ...
    // 如果压根从来不会经过的站台，就没必要计算了
    for (int i = min_city; i <= max_city; i++) {
        stations[i].vis += stations[i - 1].vis;
    }
}