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

· · 题解

一种更新的方法。

45 分的朴素做法：

首先，给所有的文件按照排序，并且对于每一个打印机，我们使他们初始的可以使用的时间为零。
然后，对于每一次打印操作，枚举每个文件和每个打印机求出最小值。

但是，这个算法最坏情况的时间复杂度是 O(nm + n \log n)，瓶颈在找最小值。

考虑优化

100 分做法：

我们可以用线段树维护打印机结束打印的时间和编号。
其中以结束打印的时间为下标。
通过区间查询 [0, ti] 获取答案。
但是，最大的时间可能到 2 \times {10}^{14}，
所以考虑用动态开点线段树解决这个问题。
对于一个节点存储多个点的时候，直接用一个小根堆处理。
其他均按 45 分暴力做法做即可。

最好时间复杂度 O(n \log n + (50 + \log n) n)。

最坏时间复杂度 O(n \log n + (50 \log m + \log n) n)。

上代码：

#include <bits/stdc++.h>
#define mid ((root->l + root->r) >> 1ll)
#define int long long
using namespace std;
const int N = 200005;
int n, m, t[N], ti;
struct pii
{
    int a, b, c;
}s[N];
struct node
{
    int minn, l, r;
    priority_queue <int, vector <int>, greater<int> > p;
    node *lef, *rig;
} *r;
multiset <int> ss; 
vector <int> f[N];
bool cmp (pii a, pii b)
{
    return a.b == b.b ? a.a < b.a : a.b < b.b;
}
//上传 
void update(node *root, int x, int num)
{
    if (root->l == root->r)
    {
        root->p.push(num);
        root->minn = root->p.top();
        return;
    }
    if (x > mid)
    {
        if (root->rig == NULL)
        {
            node *y = new node;
            y->lef = y->rig = NULL;
            y->l = mid + 1ll;
            y->r = root->r;
            root->rig = y;
        }
        update(root->rig, x, num);
        if (root->lef == NULL)
            root->minn = root->rig->minn;
        else
            root->minn = min(root->lef->minn, root->rig->minn);
    }
    else
    {
        if (root->lef == NULL)
        {
            node *y = new node;
            y->lef = y->rig = NULL;
            y->l = root->l;
            y->r = mid;
            root->lef = y;
        }
        update(root->lef, x, num);
        if (root->rig == NULL)
            root->minn = root->lef->minn;
        else
            root->minn = min(root->lef->minn, root->rig->minn);
    }
    return;
}
//删除 
bool del(node *root, int x)
{
    if (root->l == root->r)
    {
        root->p.pop();
        if (!root->p.empty())
            root->minn = root->p.top();
        return root->p.empty();
    }
    if (x > mid)
    {
        bool t = del(root->rig, x);
        if (t)
            free(root->rig), root->minn = (1ll << 50ll), root->rig = NULL;
        else
            root->minn = root->rig->minn;
        if (root->lef == NULL)
            return t;
        else
            root->minn = min(root->minn, root->lef->minn);
        return false;
    }
    else
    {
        bool t = del(root->lef, x);
        if (t)
            free(root->lef), root->minn = (1ll << 50ll), root->lef = NULL;
        else
            root->minn = root->lef->minn;
        if (root->rig == NULL)
            return t;
        else
            root->minn = min(root->minn, root->rig->minn);
        return false;
    }
}
//区间查询 
int query(node *root, int x)
{
    if (root->r <= x)
        return root->minn;
    if (root->l == root->r && root->r > x)
        return (1ll << 50ll);
    int pp = (1ll << 50ll);
    if (x > mid && root->rig != NULL)
        pp = min(pp, query(root->rig, x));
    if (x >= root->l && root->lef != NULL)
        pp = min(pp, query(root->lef, x));
    return pp;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &s[i].a, &s[i].b), s[i].c = i;
    sort(s + 1, s + 1 + n, cmp);
    r = new node;
    r->minn = (1ll << 50ll);
    r->l = 0;
    r->r = (1ll << 50ll);
    r->rig = r->lef = NULL;
    for (int i = 1; i <= m; i++)
        ss.insert(0), update(r, 0, i); //用 multiset 存储深度 
    for (int i = 1; i <= n; i++)
    {
        ti = max((long long)(*(ss.begin())), (long long)s[i].b);
        int u = query(r, ti);
        del(r, t[u]);
        ss.erase(--ss.upper_bound(t[u]));
        t[u] = (long long)(ti) + (long long)(s[i].a); // t 数组用于存储深度 
        f[u].push_back(s[i].c); // vector 数组记录 
        ss.insert(t[u]);
        update(r, t[u], u); // 上传 
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%lld", f[i].size());
        sort(f[i].begin(), f[i].end()); // 排序后输出 
        for (auto j : f[i])
            printf(" %lld", j);
        printf("\n");
    }
}