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

思路

考虑直接维护每台打印机的等待时间，线段树上二分查找最小值的最小编号。

先把文件按 t_i 排序，每次给全局减上 t_i-t_{i-1}（注意要和 0 取 max）。然后线段树上二分找到要使用的打印机。最后再给要使用的这台单点加一就行了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-')f = -f;
        c = getchar();
    }
    while(c <= '9' && c >= '0') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
void write(int x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    } if(x > 9)write(x / 10);
    putchar((x % 10) + '0');
}
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, minn[N << 2], lazy[N << 2];
struct Node {
    int s, t, id;
}a[N];
bool cmp(Node x, Node y) {
    return x.t < y.t;
}
vector<int>ans[N];
void pushup(int pos) {
    minn[pos] = min(minn[pos << 1], minn[pos << 1 | 1]);
}
void pushdown(int pos) {
    if(lazy[pos]) {
        minn[pos << 1] = max(minn[pos << 1] + lazy[pos], 0ll);
        minn[pos << 1 | 1] = max(minn[pos << 1 | 1] + lazy[pos], 0ll);
        lazy[pos << 1] += lazy[pos], lazy[pos << 1 | 1] += lazy[pos];
        lazy[pos] = 0;
    }
}
void add(int pos, int l, int r, int L, int R, int k) {
    if(L <= l && r <= R) {
        minn[pos] = max(minn[pos] + k, 0ll);
        lazy[pos] += k;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(pos);
    if(L <= mid)add(pos << 1, l, mid, L, R, k);
    if(mid + 1 <= R)add(pos << 1 | 1, mid + 1, r, L, R, k);
    pushup(pos);
}
int query(int pos, int l, int r) {
    if(l == r)return l;
    int mid = (l + r) >> 1;
    pushdown(pos);
    if(minn[pos << 1] <= minn[pos << 1 | 1])return query(pos << 1, l, mid);
    return query(pos << 1 | 1, mid + 1, r);
}
signed main() {
    //freopen("print.in", "r", stdin);
    //freopen("print.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; i++)a[i].s = read(), a[i].t = read(), a[i].id = i;
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i++) {
        add(1, 1, m, 1, m, -(a[i].t - a[i - 1].t));
        int idx = query(1, 1, m);
        ans[idx].push_back(a[i].id);
        add(1, 1, m, idx, idx, a[i].s);
    }
    for(int i = 1; i <= m; i++) {
        sort(ans[i].begin(), ans[i].end());
        write(ans[i].size());
        putchar(' ');
        for(int j = 0; j < ans[i].size(); j++) {
            write(ans[i][j]);
            if(j != ans[i].size() - 1)putchar(' ');
        }
        if(i != m)putchar('\n');
    }
    return 0;
}