充电宝的高效率流转

题意

配送站有 个充电宝（编号 到 ）， 位骑手按各自的到达时间依次换电。每位骑手到达时，把耗尽的电池放入一个充电宝充电（需要 时间），同时从当前所有可用的充电宝中取走编号最小的那个。问：第 位骑手最终拿到的是几号充电宝？

思路

先想清楚"可用"是什么意思。骑手在时刻 到达，从编号最小的空闲充电宝取走电池，同时放入自己的旧电池充电。这个充电宝在 时刻才会重新变成可用。

关键观察： 如果我们把骑手按到达时间排序，那么处理到某位骑手时，所有释放时间 的充电宝都已经充好电了，可以重新被选。

这不就是一个经典的"事件模拟 + 两个堆"的结构吗？

  • 可用堆（小根堆，按编号）：存放当前空闲的充电宝编号，初始放入 。
  • 忙碌堆（小根堆，按释放时间）：存放正在充电的 。

每来一位骑手（时刻 ）：

  1. 把忙碌堆中所有释放时间 的充电宝弹出，放回可用堆。
  2. 从可用堆弹出堆顶（编号最小的），就是这位骑手拿到的充电宝。
  3. 把这个充电宝以 的形式推入忙碌堆。

处理到第 位骑手时直接输出答案即可。

为什么排序后贪心是对的？ 所有到达时间互不相同，排序后就是真实的时间线。每一步只需要看"此刻哪些充电宝已经充好了"，这由释放时间决定，和后面的骑手无关——标准的在线模拟。

复杂度

  • 时间：，排序 ，每次堆操作 。
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vector<int> arr(m), chg(m);
    for(int i = 0; i < m; i++) scanf("%d%d", &arr[i], &chg[i]);
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){ return arr[a] < arr[b]; });

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

    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> busy;

    for(int i = 0; i < m; i++){
        int ri = idx[i];
        long long t = arr[ri];
        while(!busy.empty() && busy.top().first <= t){
            avail.push(busy.top().second);
            busy.pop();
        }
        int c = avail.top(); avail.pop();
        busy.push({t + chg[ri], c});
        if(ri + 1 == k){
            printf("%d\n", c);
            return 0;
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[m], chg = new int[m];
        for (int i = 0; i < m; i++) {
            arr[i] = sc.nextInt();
            chg[i] = sc.nextInt();
        }
        Integer[] idx = new Integer[m];
        for (int i = 0; i < m; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> arr[a] - arr[b]);

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

        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) ->
            a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));

        for (int i = 0; i < m; i++) {
            int ri = idx[i];
            long t = arr[ri];
            while (!busy.isEmpty() && busy.peek()[0] <= t) {
                avail.add((int) busy.poll()[1]);
            }
            int c = avail.poll();
            busy.add(new long[]{t + chg[ri], c});
            if (ri + 1 == k) {
                System.out.println(c);
                return;
            }
        }
    }
}

import heapq
import sys
input = sys.stdin.readline

def main():
    n, m, k = map(int, input().split())
    riders = []
    for i in range(m):
        a, c = map(int, input().split())
        riders.append((a, c, i))

    riders.sort()

    avail = list(range(1, n + 1))
    heapq.heapify(avail)
    busy = []

    for a, c, orig in riders:
        while busy and busy[0][0] <= a:
            _, charger = heapq.heappop(busy)
            heapq.heappush(avail, charger)
        charger = heapq.heappop(avail)
        heapq.heappush(busy, (a + c, charger))
        if orig + 1 == k:
            print(charger)
            return

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const [n, m, k] = lines[0].split(' ').map(Number);
    const riders = [];
    for (let i = 0; i < m; i++) {
        const [a, c] = lines[i + 1].split(' ').map(Number);
        riders.push([a, c, i]);
    }
    riders.sort((a, b) => a[0] - b[0]);

    class MinHeap {
        constructor(cmp) { this.h = []; this.cmp = cmp; }
        push(v) { this.h.push(v); this._up(this.h.length - 1); }
        pop() { const top = this.h[0]; const last = this.h.pop(); if (this.h.length > 0) { this.h[0] = last; this._down(0); } return top; }
        peek() { return this.h[0]; }
        get size() { return this.h.length; }
        _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.cmp(this.h[i], this.h[p]) < 0) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; } else break; } }
        _down(i) { const n = this.h.length; while (true) { let s = i, l = 2*i+1, r = 2*i+2; if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l; if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r; if (s === i) break; [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s; } }
    }

    const avail = new MinHeap((a, b) => a - b);
    for (let i = 1; i <= n; i++) avail.push(i);
    const busy = new MinHeap((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);

    for (const [a, c, orig] of riders) {
        while (busy.size > 0 && busy.peek()[0] <= a) {
            avail.push(busy.pop()[1]);
        }
        const charger = avail.pop();
        busy.push([a + c, charger]);
        if (orig + 1 === k) {
            console.log(charger);
            return;
        }
    }
});