题解：P14191 [ICPC 2024 Hangzhou R] Elevator II

kill_dependency · 2025-10-11 21:14:45 · 题解

题目大意

有一部电梯每次只能乘坐 1 人，上升消耗 r - l，下降无消耗，问把所有人送到目的地的最小消耗之和并给出安排方案。

解题思路

先让电梯升到最高处，上升过程中的人能送就送（他们都是去往最高处途中顺手的事）,然后按照 r 降序送，这样保证了当前这个 r 不会再来，不会有浪费，途中记录一下乘客在原序列的中的位置最后输出即可。

代码实现

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t;
    std::cin >> t;

    while (t--) {
        int n, f;
        std::cin >> n >> f;

        std::vector<std::array<int, 3>> lr(n);
        for (int i = 0; i < n; i++) {
            std::cin >> lr[i][0] >> lr[i][1];
            lr[i][2] = i + 1;
        }

        std::sort(lr.begin(), lr.end());

        i64 ans = 0;
        std::vector<int> ord, F(n);
        for (int i = 0; i < n; i++) {
            auto [l, r, idx] = lr[i];
            if (l < f) {
                if (r > f) {
                    f = r;
                    ans += r - l;
                    ord.push_back(idx);
                    F[idx - 1] = 1;
                }
                continue;
            }
            if (l > f) {
                ans += l - f;
            }
            f = r;
            ans += r - l;
            ord.push_back(idx);
            F[idx - 1] = 1;
        }

        std::sort(lr.begin(), lr.end(), [&](std::array<int, 3> a, std::array<int, 3> b) { return a[0] > b[0]; });

        for (int i = 0; i < n; i++) {
            auto [l, r, idx] = lr[i];
            if (F[idx - 1]) {
                continue;
            }
            f = r;
            ans += r - l;
            ord.push_back(idx);
            F[idx - 1] = 1;
        }

        std::cout << ans << "\n";
        for (int i = 0; i < n; i++) {
            std::cout << ord[i] << " \n"[i == n - 1];
        }
    }
}