专栏文章

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

kkill_dependency
P14191题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmshoh
此快照首次捕获于
2025/12/02 04:58
3 个月前
此快照最后确认于
2025/12/02 04:58
3 个月前
查看原文

题目大意

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

解题思路

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

代码实现

CPP
#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];
        }
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...