L3-017 森森快递 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。

公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。

为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。

输入格式：

输入在第一行给出两个正整数N和Q（2≤N≤105, 1≤Q≤105），表示总共的城市数以及订单数量。

第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量Ci（i=0,⋯,N−2）。题目保证每个Ci是不超过231的非负整数。

接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。

输出格式：

在一行中输出可运输货物的最大重量。

输入样例：

10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2

输出样例：

样例提示：我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。

分析：每个路程受到其中最小承重量限制，不同的运输路线[a, b]，[c，d]之间有3种关系 1.[a, b]与[c，d]无交集，则可以同时进行两个运输订单 2.如果一个路线包含于另一个路线中，那么选择少的那一段显然更优 3.[a, b]与[c，d]存在交集，交集为[c，b]，则能最大运输货物重量为min([c，b]，[a，c] + [b，d]。综上，我们可以将点坐标，按照右端点从小到大的顺序排列，相等的情况下，按照左端点从小到大的顺序排列。只需要建立一棵具有区间加以及区间最小值的线段树即可，符合结分配合律，故不需要lazy数组。遍历排序后的接线信息，每个路线取到最大运输货物后，减少本线路的通货承重量，即可得到最终答案～

注意：输入的路线起始与结束不一定小的在前面，大的在后面～

#include <bits/stdc++.h>
#define Lx(a) (a << 1) + 1
#define Rx(a) (a << 1) + 2
using namespace std;
int n, m, Size;
long long ans, temp;
pair<int, int> B[100000];
struct segtree {
    vector<long long> values, mins;
    void init(int n) {
        Size = 1;
        while (Size < n) Size *= 2;
        values.assign(2 * Size, 0LL);
        mins.assign(2 * Size, 0LL);
        build(0, 0, Size, n);
    }
    void build(int x, int lx, int rx, int R) {
        if (rx - lx == 1) {
            if (lx < R) {
                cin >> mins[x];
                values[x] = mins[x];
            }
            return;
        }
        int mid = lx + rx >> 1;
        build(Lx(x), lx, mid, R);
        build(Rx(x), mid, rx, R);
        mins[x] = min(mins[Lx(x)], mins[Rx(x)]) + values[x];
    }
    void modify(int l, int r, int v, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            mins[x] += v;
            values[x] += v;
            return;
        }
        int mid = lx + rx >> 1;
        modify(l, r, v, Lx(x), lx, mid);
        modify(l, r, v, Rx(x), mid, rx);
        mins[x] = min(mins[Lx(x)], mins[Rx(x)]) + values[x];
        return;
    }
    long long get_min(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return LLONG_MAX;
        if (lx >= l && rx <= r) return mins[x];
        int mid = lx + rx >> 1;
        long long s1 = get_min(l, r, Lx(x), lx, mid);
        long long s2 = get_min(l, r, Rx(x), mid, rx);
        return min(s1, s2) + values[x];
    }
}st;
bool cmp (const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}
int main() {
    cin >> n >> m;
    st.init(--n);
    for (int i = 0; i < m; i++) {
        cin >> B[i].first >> B[i].second;
        if (B[i].first > B[i].second) swap(B[i].first, B[i].second);
    }
    sort(B, B + m, cmp);
    for (int i = 0; i < m; i++) {
        temp = st.get_min(B[i].first, B[i].second, 0, 0, Size);
        ans += temp;
        st.modify(B[i].first, B[i].second, -temp, 0, 0, Size);
    }
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>

#define Lx(a) (a << 1) + 1

#define Rx(a) (a << 1) + 2

using namespace std;

int n, m, Size;

long long ans, temp;

pair<int, int> B[100000];

struct segtree {

vector<long long> values, mins;

void init(int n) {

Size = 1;

while (Size < n) Size *= 2;

values.assign(2 * Size, 0LL);

mins.assign(2 * Size, 0LL);

build(0, 0, Size, n);

}

void build(int x, int lx, int rx, int R) {

if (rx - lx == 1) {

if (lx < R) {

cin >> mins[x];

values[x] = mins[x];

}

return;

}

int mid = lx + rx >> 1;

build(Lx(x), lx, mid, R);

build(Rx(x), mid, rx, R);

mins[x] = min(mins[Lx(x)], mins[Rx(x)]) + values[x];

}

void modify(int l, int r, int v, int x, int lx, int rx) {

if (lx >= r || rx <= l) return;

if (lx >= l && rx <= r) {

mins[x] += v;

values[x] += v;

return;

}

int mid = lx + rx >> 1;

modify(l, r, v, Lx(x), lx, mid);

modify(l, r, v, Rx(x), mid, rx);

mins[x] = min(mins[Lx(x)], mins[Rx(x)]) + values[x];

return;

}

long long get_min(int l, int r, int x, int lx, int rx) {

if (lx >= r || rx <= l) return LLONG_MAX;

if (lx >= l && rx <= r) return mins[x];

int mid = lx + rx >> 1;

long long s1 = get_min(l, r, Lx(x), lx, mid);

long long s2 = get_min(l, r, Rx(x), mid, rx);

return min(s1, s2) + values[x];

}

}st;

bool cmp (const pair<int, int> &a, const pair<int, int> &b) {

if (a.second != b.second) return a.second < b.second;

return a.first < b.first;

}

int main() {

cin >> n >> m;

st.init(--n);

for (int i = 0; i < m; i++) {

cin >> B[i].first >> B[i].second;

if (B[i].first > B[i].second) swap(B[i].first, B[i].second);

}

sort(B, B + m, cmp);

for (int i = 0; i < m; i++) {

temp = st.get_min(B[i].first, B[i].second, 0, 0, Size);

ans += temp;

st.modify(B[i].first, B[i].second, -temp, 0, 0, Size);

}

cout << ans;

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版