题解：P11289 【MX-S6-T1】「KDOI-11」打印

「KDOI-11」打印

看到这题，第一反应感觉比较水，感觉直接把每个打印机的“最后使用时间-编号”插入一个 std::set 中，按照时间将任务排序后每次选取 begin() 所表示的打印机。

但是这样过不了样例，因为这样第一关键字是最后一次打印时间而非等待时间，即等待时间为上次打印时间减去使用时间，对 0 取最大值，即负值视为 0。

有一个比较暴力的想法，每次暴力将不到当前时间的打印机改为当前时间，时间复杂度 O(n^2\log n)，实测能过 60 分。

for (int tmp, i = 1; i <= n; ++i) {
    const auto &[p, s, t] = w[i];
    while (set.begin()->first < t)
      tmp = set.begin()->second, set.erase({set.begin()}), set.insert({t, tmp});
    const auto &[tim, id] = *set.begin();
    set.erase(set.begin()), vec[id]->push_back(p);
    set.insert({std::max(tim, t) + s, id});
  }
  for (int i = 1; i <= m; ++i) {
    cout << vec[i]->size();
    std::sort(vec[i]->begin(), vec[i]->end());
    for (const int &j : *vec[i]) cout << ' ' << j;
    cout << '\n';
  }

然后考虑这样写，时间复杂度太大的原因主要在枚举打印时间小于当前时间的打印机，考虑用某种方式消除。每次都修改不如查询时取 \min，考虑使用线段树，线段树上的一个叶子节点表示一个打印机。维护区间最小值，那么选取一个区间内的打印机，最小的等待时间就可以通过 std::max(0LL, tr[p].min - t) 求得。每次插入时在线段树上二分，以等待时间为第一关键字选择子节点选取，如果相同选择左半部分，即编号更小的打印机。

线段树二分是没有区间限制的那种，剩下的都是板子，没什么细节，感觉很简单，记得开 long long。代码见此。