题解：#8757.景点观光 - 帖子

对于每个景点的选择，我们需要考虑当前景点所需的时间，包括从原点出发的路程时间和观光时间。

由于问题涉及到最大化观光景点的数量，可以考虑使用 优先队列(最大堆)~ 来优化选择。

在遍历每个景点时，我们先计算当前景点的旅行和观光所需的总时间。

如果总时间超过了给定时间，我们将优先去掉耗时最长的景点（即最大堆中的最大元素），以腾出更多时间给后续景点。

这样做可以确保我们在给定时间内尽可能多地参观景点。

使用 priority_queue（最大堆）来存储已经参观的景点的观光时间。

对于每个景点，计算它到达的总时间，并将其加入堆中。

如果总时间超过了，我们从堆中取出一个观光时间最长的景点，减去其时间，使得总时间回到允许范围内。

最终，我们记录下可以参观的最大景点数。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 定义一个结构体来存储每个景点的位置(x)和观光时间(t)
struct Spot {
    int x, t;  // x 表示景点的位置，t 表示景点的观光时间
};

int main() {
    int n, p;
    cin >> n >> p;  // 输入景点数量 n 和总时间 p

    vector<Spot> spots(n);  // 定义一个大小为 n 的 vector 来存储所有景点
    for (int i = 0; i < n; ++i) {
        cin >> spots[i].x >> spots[i].t;  // 输入每个景点的位置 x 和观光时间 t
    }

    priority_queue<int> maxHeap;  // 定义一个最大堆，用来存储已参观景点的观光时间
    int totalTime = 0, maxSpots = 0;  // totalTime 用来记录当前总时间，maxSpots 用来记录最多能参观的景点数

    for (int i = 0; i < n; ++i) {
        // 计算从上一个景点到当前景点的路程时间
        int travelTime = (i == 0) ? spots[i].x : spots[i].x - spots[i - 1].x;

        // 更新总时间，包含旅行时间和当前景点的观光时间
        totalTime += travelTime + spots[i].t;

        // 将当前景点的观光时间加入最大堆
        maxHeap.push(spots[i].t);

        // 如果总时间超过了 p，则移除最耗时的景点，减小总时间
        while (totalTime > p && !maxHeap.empty()) {
            totalTime -= maxHeap.top();  // 从总时间中减去堆顶元素（最耗时的景点的时间）
            maxHeap.pop();  // 移除堆顶元素
        }

        // 更新可以参观的最大景点数
        maxSpots = max(maxSpots, int(maxHeap.size()));  // 堆中保存的是已参观景点的观光时间，堆的大小即为已参观景点的数目
    }

    cout << maxSpots << endl;  // 输出最多能参观的景点数
    return 0;
}

题解：#8757.景点观光 审核通过

题解：#8757.景点观光审核通过