P3406 海底高铁

(不要小看了这个数据范围)

首先明确一下题意,对于样例中的访问顺序3 1 4 1 5 9 2 6 5 3,它意味着:(数字代表城市)

从 3 出发,依次经过2~3间的铁路,1~2间的铁路,到达1;

再从 1 出发,依次经过1~2,2~3,3~4之间的铁路,到达4,以此类推.

显然,对于任意一段铁路,可以根据访问顺序统计出来经过他们的次数,而仅仅通过这个次数就可以计算出来是直接买票还是买卡后买票比较划算.

设第i段铁路经过的次数为p[i],那么遍历铁路1~n-1(注意只有n-1段铁路,第i段铁路从i城到达i+1城),使ans += min(p[i] * a[i], p[i] * b[i] + c[i])即可.

---

现在逐个解决问题,如何统计每一段次数经过的次数?
暴力方法是读入起点和终点城市,然后让其间涉及到的p[i]加一,这里明显会TLE,

所以使用差分,差分是一种与前缀和相对的预处理方法:

对于读入的一对起点城市from和终点城市to,有(根据题意from 不会与to相等)

    cin >> from;
    for(int i = 2; i <= m; i++){
        cin >> to;
        p[min(from, to)]++;
        p[max(from, to)]--;
        from = to;
    }

读入访问所有访问顺序后,进行前缀和处理:

    for(int i = 1; i <= n; i++) p[i] += p[i - 1];

此时,p[i]就可以表示通过铁路i的次数了,这里的复杂度(为O(n))比暴力统计(最坏情况O(n²),即这个人从1到n反复横跳)小很多.

这里的差分应当是很容易理解的.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, m, p[100010], a[100010], b[100010], c[100010];
unsigned long long ans;

void calc(){    // 我本以为这会是个稍微花费点功夫的函数
    for(int i = 1; i < n; i++)
        ans += min((long long)p[i] * a[i], (long long)p[i] * b[i] + c[i]);
}

int main(){
    // freopen("in.txt", "r", stdin);    // 忘记注释见祖宗
    int from, to;
    cin >> n >> m;
    cin >> from;
    for(int i = 2; i <= m; i++){
        cin >> to;
        p[min(from, to)]++;
        p[max(from, to)]--;
        from = to;
    }
    for(int i = 1; i <= n; i++) p[i] += p[i - 1];
    for(int i = 1; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    calc();

    cout << ans << endl;

    return 0;
}    

---

在我AC之前,这里还有一个我个人所犯的错误.

尽管为了防爆给ans开了long long,当我发现数组p只需要int就可以存储时就认为这样写很合理:

void calc(){
    for(int i = 1; i < n; i++)
        ans += min(p[i] * a[i], p[i] * b[i] + c[i]);
}

结果犯了个初学者的错误,右侧表达式的最高等级是int,但实际上int的乘积是需要long long来正确存储的,需要强制类型转换.即

void calc(){
    for(int i = 1; i < n; i++)
        ans += min((long long)p[i] * a[i], (long long)p[i] * b[i] + c[i]);
}