题目链接

充电宝的高效率流转

题目描述

在一个外卖站，有 个充电宝（编号 1 到 ）和 位骑手（按输入顺序编号 1 到 ）。骑手们会按各自的到达时间点来更换电池。

换电规则:

  1. 骑手按各自的到达时间先后顺序进行操作。
  2. 当一位骑手到达时，他会从当前所有可用的充电宝中，选择编号最小的一个来使用。
  3. 该充电宝被占用后，会进入充电状态，并在 当前时间 + 充电时间 后再次变为可用。

你需要找出按输入顺序编号为 的那位骑手，最终使用了哪个编号的充电宝。

输入:

  • 第一行：。
  • 接下来 行：按骑手编号 1 到 的顺序，每行给出该骑手的 到达时间 和 充电时间。

输出:

  • 一个整数，代表编号为 的骑手所使用的充电宝编号。

解题思路

这是一个典型的事件驱动模拟问题。核心思想是不能按骑手的输入顺序处理，而必须严格按照时间顺序来模拟整个事件流程。我们需要高效地管理充电宝的两种状态：“可用”和“占用中”。

  1. 事件排序

    • 首先，我们需要将所有骑手的换电请求视为一个个独立的事件。由于事件必须按时间顺序发生，所以第一步是将所有骑手的信息（包括他们的原始编号、到达时间、充电时间）读入后，按到达时间升序排序。

  2. 状态管理

    • 我们需要两个数据结构来动态维护充电宝池的状态：
      • 可用充电宝池: 存放当前所有可用的充电宝编号。根据规则，骑手总是选择编号最小的，因此一个最小堆（Min-Priority Queue） 是最理想的数据结构。
      • 占用充电宝池: 存放正在充电的充电宝。我们需要知道它们何时会变回可用状态。因此，可以用另一个最小堆来存储 (可用时间点, 充电宝编号) 的二元组，并按“可用时间点”排序。

  3. 模拟流程

    • 初始化:
      • 将所有 个充电宝（编号 1 到 ）放入“可用充电宝池”的最小堆中。
      • “占用充电宝池”的最小堆初始为空。
    • 处理事件: 遍历按时间排好序的骑手列表。对于每个骑手： a. 推进时间: 获取当前骑手的到达时间 current_time。 b. 释放充电宝: 查看“占用充电宝池”堆顶的元素。如果堆顶充电宝的“可用时间点”小于或等于 current_time，说明它在当前骑手到达时或之前已经充电完成。将其从占用堆中弹出，并将其编号放回可用堆。重复此步骤，直到占用堆为空或堆顶元素的可用时间点大于 current_time。 c. 分配充电宝: 从“可用充电宝池”的堆顶取出一个元素，这就是当前骑手能拿到的编号最小的可用充电宝。 d. 记录结果: 如果当前骑手的原始编号是 ，那么上一步取出的充电宝编号就是我们要求的答案。 e. 更新状态: 计算新占用的充电宝将来的可用时间点 current_time + 充电时间，然后将 (新可用时间点, 充电宝编号) 存入“占用充电宝池”的最小堆中。

  4. 输出:

    • 遍历完所有骑手后，输出记录下的目标骑手 所使用的充电宝编号。

代码

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

using namespace std;

struct Rider {
    int id;
    int arrival_time;
    int charge_time;
};

struct Occupied {
    int free_time;
    int bank_id;
    bool operator>(const Occupied& other) const {
        return free_time > other.free_time;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, p;
    cin >> n >> m >> p;

    vector<Rider> riders(m);
    for (int i = 0; i < m; ++i) {
        riders[i].id = i + 1;
        cin >> riders[i].arrival_time >> riders[i].charge_time;
    }

    sort(riders.begin(), riders.end(), [](const Rider& a, const Rider& b) {
        return a.arrival_time < b.arrival_time;
    });

    priority_queue<int, vector<int>, greater<int>> available_banks;
    for (int i = 1; i <= n; ++i) {
        available_banks.push(i);
    }

    priority_queue<Occupied, vector<Occupied>, greater<Occupied>> occupied_banks;
    int target_rider_bank_id = -1;

    for (const auto& rider : riders) {
        int current_time = rider.arrival_time;
        
        while (!occupied_banks.empty() && occupied_banks.top().free_time <= current_time) {
            available_banks.push(occupied_banks.top().bank_id);
            occupied_banks.pop();
        }

        int chosen_bank = available_banks.top();
        available_banks.pop();

        if (rider.id == p) {
            target_rider_bank_id = chosen_bank;
        }

        occupied_banks.push({current_time + rider.charge_time, chosen_bank});
    }

    cout << target_rider_bank_id << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Comparator;

class Rider {
    int id;
    int arrivalTime;
    int chargeTime;

    Rider(int id, int arrivalTime, int chargeTime) {
        this.id = id;
        this.arrivalTime = arrivalTime;
        this.chargeTime = chargeTime;
    }
}

class Occupied {
    int freeTime;
    int bankId;

    Occupied(int freeTime, int bankId) {
        this.freeTime = freeTime;
        this.bankId = bankId;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();

        List<Rider> riders = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            riders.add(new Rider(i + 1, sc.nextInt(), sc.nextInt()));
        }

        riders.sort(Comparator.comparingInt(r -> r.arrivalTime));

        PriorityQueue<Integer> availableBanks = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            availableBanks.add(i);
        }

        PriorityQueue<Occupied> occupiedBanks = new PriorityQueue<>(Comparator.comparingInt(o -> o.freeTime));
        int targetRiderBankId = -1;

        for (Rider rider : riders) {
            int currentTime = rider.arrivalTime;

            while (!occupiedBanks.isEmpty() && occupiedBanks.peek().freeTime <= currentTime) {
                availableBanks.add(occupiedBanks.poll().bankId);
            }

            int chosenBank = availableBanks.poll();

            if (rider.id == p) {
                targetRiderBankId = chosenBank;
            }

            occupiedBanks.add(new Occupied(currentTime + rider.chargeTime, chosenBank));
        }

        System.out.println(targetRiderBankId);
    }
}

import heapq

def main():
    n, m, p = map(int, input().split())
    riders = []
    for i in range(m):
        arrival, charge = map(int, input().split())
        riders.append({'id': i + 1, 'arrival': arrival, 'charge': charge})

    # 按到达时间对骑手排序
    riders.sort(key=lambda r: r['arrival'])

    # 可用充电宝，最小堆
    available_banks = list(range(1, n + 1))
    heapq.heapify(available_banks)
    
    # 占用中充电宝 (free_time, bank_id)，最小堆
    occupied_banks = []
    
    target_rider_bank_id = -1

    for rider in riders:
        current_time = rider['arrival']

        # 释放到点的充电宝
        while occupied_banks and occupied_banks[0][0] <= current_time:
            _, bank_id = heapq.heappop(occupied_banks)
            heapq.heappush(available_banks, bank_id)

        # 分配编号最小的充电宝
        chosen_bank = heapq.heappop(available_banks)

        if rider['id'] == p:
            target_rider_bank_id = chosen_bank
        
        # 将新占用的充电宝放入占用堆
        new_free_time = current_time + rider['charge']
        heapq.heappush(occupied_banks, (new_free_time, chosen_bank))
        
    print(target_rider_bank_id)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：事件驱动模拟、优先队列（堆）
  • 时间复杂度：。
    • 对 个骑手按到达时间排序需要 。
    • 主循环遍历 个骑手。在循环内部，涉及对两个优先队列的操作。优先队列的大小最多为 ，因此每次操作（入队/出队）的复杂度是 。总的模拟过程复杂度为 。
  • 空间复杂度：。
    • 用于存储所有骑手的信息。
    • 用于存储两个优先队列中的充电宝状态。