CF1945G G. Cook and Porridge题解

G. Cook and Porridge

题目翻译

​ 题目给我们n个排着队的学生，每个学生都有一个优先级和吃饭时间，初始时按照1到n排序，每一秒在最前面的学生可以得到吃的，然后他会花费s[i]的吃饭时间吃饭，记录当前时间为x，则他会在x + s[i]的时刻结束时回来排队，此时对尾所有优先即严格低于他的学生都会被他插队，直到遇到优先级大于等于他的。我们需要计算1到d秒内所有学生都吃过一回饭的最小时刻，或者报告不可能。

思路

​ 注意到d的数据范围很小，同时每个时刻只有一个学生会吃饭，所以归队的学生也最多d个，考虑模拟这个过程。我们发现因为初始状态的优先级不是单调的我们很难处理，但是我们可以注意到每次插入后当前元素所在的那个小块一定是优先级别大到小的递减的。所以我们考虑维护初始状态的后缀最大值，我们每次学生归队时通过二分找出他会被拦截在哪个块的后面，然后在这个块的后面插入，此时每个块中的元素都是优先级单调的，我们可以直接使用set维护即可，每一块中优先级大的靠钱，相同则比较插入时间，插入时间小的考前。我们在开一个set维护哪几个块中有元素即可取出队首的元素。记录每个学生是否吃过饭，全吃过记录答案退出即可。

​ 另外一种比较简单的实现方式是直接使用平衡树，注意到如果初始队列的优先级别是单调的我们直接使用一个优先队列即可维护。我们发现插入的规则是固定的，但初始的元素可能不满足这个规则，我们可以直接用平衡树手动初始化节点，最后按照规则插入即可。具体的可以维护每个子树内节点的优先级最大值，队首就是最左侧存活的节点。我的代码使用的替罪羊树进行实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//set维护
struct node{
    int offset;
    int id;
    int ci;
};

void solve(){
    int n, d;
    std::cin >> n >> d;
    std::vector<int> k(n + 1, 0);
    std::vector<int> s(n + 1, 0);
    for(int i = 1; i <= n; i++){
        std::cin >> k[i] >> s[i];
    }

    std::vector<int> suf(n + 2, 0);
    std::vector<int> res;
    for(int i = n; i >= 1; i--){
        suf[i] = std::max(suf[i + 1], k[i]);
        res.push_back(suf[i]);
    }

    auto cmp = [&](std::pair<int, int> a, std::pair<int, int> b){
        if(k[a.ff] != k[b.ff])
            return k[a.ff] > k[b.ff];
        return a.ss < b.ss;
    };

    std::vector<std::set<std::pair<int, int>, decltype(cmp)>> pos(n + 1, std::set<std::pair<int, int>, decltype(cmp)>(cmp));
    //[id, cha]
    std::set<int> se;   //pos who has num
    for(int i = 1; i <= n; i++){
        pos[i].insert({i, i});
        se.insert(i);
    }
    int cha = n + 1;

    int ans = 0;
    std::vector<int> vis(n + 1, false);
    std::vector<std::vector<int>> time(d + 1);
    int cnt = 0;
    for(int i = 1; i <= d; i++){
        int who = *se.begin();
        auto p = *pos[who].begin();
        pos[who].erase(p);
        if(pos[who].size() == 0){
            se.erase(who);
        }

        if(!vis[p.ff]){
            vis[p.ff] = true;
            cnt += 1;
        }
        if(i + s[p.ff] <= d){
            time[i + s[p.ff]].push_back(p.ff);
        }

        std::sort(time[i].begin(), time[i].end(), [&](auto a, auto b){
            return s[a] < s[b];
        });
        for(auto x : time[i]){
            int now = k[x];
            int ind = std::lower_bound(res.begin(), res.end(), now) - res.begin();
            int qu = n - ind;
            pos[qu].insert({x, cha});
            if(pos[qu].size() == 1){
                se.insert(qu);
            }
            cha += 1;
        }
        
        if(cnt == n){
            ans = i;
            break;
        }
    }
    std::cout << (ans == 0 ? -1 : ans) << endl;

}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
//平衡树维护
//该平衡树的模板根据题意重构了，部分注释可能不对，为模板原来的注释
template<class T>
class Scapegoat{
    //该模板的BST，左侧子节点的值小于等于当前节点的值
private: 
    const double alpha = 0.75;    //替罪羊树的不平衡度，通常在0.7左右

    struct Node{
        int ls, rs;
        T val;
        T id;
        T maxn;
        int tot;    //实际存储的空间，包括删除的节点
        int size;   //实际存储的节点，不包括删除的节点
        int save;   //该节点是否存活，1存活，0删除
    };

    std::vector<Node> tree;
    std::vector<int> order; //用来记录中序遍历的结果
    int cnt;    //使用数组模拟，vector当数组用减小常数
    std::vector<int> tree_stack;    //记录可用空间的栈
    int top;    //tree_stack 的栈顶
    int root;   //当前的根节点，替罪羊树中根节点会变动


    void Inorder(int u){    //中序遍历
        if(!u)
            return;
        Inorder(tree[u].ls);
        if(tree[u].save)
            order[++cnt] = u;
        else
            tree_stack[++top] = u;
        Inorder(tree[u].rs);
    }

    void Initnode(int u){
        tree[u].ls = tree[u].rs = 0;
        tree[u].size = tree[u].tot = tree[u].save = 1;
    }

    void Update(int u){
        tree[u].size = tree[tree[u].ls].size + tree[tree[u].rs].size + tree[u].save;   //注意这里是1，需要保证u存活
        tree[u].tot = tree[tree[u].ls].tot + tree[tree[u].rs].tot + 1;
        tree[u].maxn = std::max({tree[u].val, tree[tree[u].ls].maxn, tree[tree[u].rs].maxn});
    }

    void build(int l, int r, int& u){   //注意这里的u是引用
        rebuild_num++;
        int mid = (l + r) >> 1;
        u = order[mid];
        if(l == r){
            Initnode(u);
            tree[u].maxn = tree[u].val;
            return;
        }
        if(l < mid)
            build(l, mid - 1, tree[u].ls);
        if(l == mid)
            tree[u].ls = 0;
        build(mid + 1, r, tree[u].rs);
        Update(u);
    }

    void rebuild(int& u){   //重建函数，调用中序遍历的结果进行构建
        cnt = 0;
        Inorder(u);
        if(cnt)
            build(1, cnt, u);
        else
            u = 0;
    }

    bool notbalance(int u){
        //若一颗子树的占比超过了平衡率则不平衡
        if((double) tree[u].size * alpha <= (double) std::max(tree[tree[u].ls].size, tree[tree[u].rs].size))
            return true;
        return false;
    }

public:
    int rebuild_num = 0;
    /*测试使用
    int deep_timer = 0;
    int max_deep = 0;
    std::vector<int> tree_deep;

    void cnt_deep(int u){
        if(u){
            tree_deep[u] = ++deep_timer;
            max_deep = std::max(max_deep, tree_deep[u]);
            cnt_deep(tree[u].ls);
            cnt_deep(tree[u].rs);
            deep_timer--;
        }
    }
    */
    
    int Root(){
        return root;
    }

    void print_tree(int u){
        if(u){

            std::cerr << "id = " << tree[u].id << ",l = " << tree[tree[u].ls].id << ",r = " << tree[tree[u].rs].id << endl;
            std::cerr << tree[tree[u].rs].maxn << endl;

            print_tree(tree[u].ls);
            // if(tree[u].save)
            //     std::cerr << tree[u].id << space;
            print_tree(tree[u].rs);
        }
    }

    T kth(int k){     //获取第k小的数的值
        int u = root;
        while(u){
            if(tree[u].save && tree[tree[u].ls].size + 1 == k)
                return tree[u].id;
            else if(tree[tree[u].ls].size >= k)
                u = tree[u].ls;
            else{
                k -= tree[tree[u].ls].size + tree[u].save;
                u = tree[u].rs;
            }
        }
        return tree[u].id;
    }

    void Insert(int& u, T x, T id){     //插入数字x
        if(!u){
            u = tree_stack[top--];
            tree[u].val = x;
            tree[u].id = id;
            tree[u].maxn = x;
            Initnode(u);
            return;
        }
        // tree[u].size++;
        // tree[u].tot++;
        if(tree[tree[u].rs].size && tree[tree[u].rs].maxn >= x)
            Insert(tree[u].rs, x, id);
        else if(tree[u].save && tree[u].val >= x)
            Insert(tree[u].rs, x, id);
        else
            Insert(tree[u].ls, x, id);

        Update(u);

        if(notbalance(u))
            rebuild(u);
    }

    void Insert(T x, T id){
        Insert(root, x, id);
    }


    void Del_k(int& u, int k){      //删除第k大的数(直接使用不会触发重构，会有问题，需要手动控制重构)
        //tree[u].size--;
        if(tree[u].save && tree[tree[u].ls].size + 1 == k){
            tree[u].save = 0;
            tree[u].val = 0;
            tree[u].maxn = 0;
            tree[u].id = 0;
            Update(u);
            return;
        }
        if(tree[tree[u].ls].size + tree[u].save >= k)
            Del_k(tree[u].ls, k);
        else
            Del_k(tree[u].rs, k - tree[tree[u].ls].size - tree[u].save);
        Update(u);
    }

    void Del(){ //删除第一个值
        Del_k(root, 1);
        if(tree[root].tot * alpha >= tree[root].size)
            rebuild(root);      //若删除的节点过多则重构
    }

    Scapegoat(int n, std::vector<int> k){
        tree.resize(n + 1, Node());
        order.resize(n + 1, 0);
        tree_stack.resize(n + 1, 0);
        root = cnt = top = 0;
        for(int i = n; i >= 1; i--)
            tree_stack[++top] = i;

        std::function<void(int, int, int&)> init = [&](int l, int r, int& u){
            int mid = (l + r) >> 1;

            if(!u){
                u = tree_stack[top--];

                //std::cerr << u << space << mid << endl;

                tree[u].val = k[mid];
                tree[u].id = mid;
                tree[u].maxn = k[mid];
                Initnode(u);
            }

            if(l == r){
                return;
            }

            if(l < mid)
                init(l, mid - 1, tree[u].ls);
            if(l == mid)
                tree[u].ls = 0;
            init(mid + 1, r, tree[u].rs);
            Update(u);
        };
        init(1, k.size() - 1, root);
        //tree_deep.resize(n + 1, 0);
    }
    Scapegoat(int n, double new_alpha){
        alpha = new_alpha;
        tree.resize(n + 1, Node());
        order.resize(n + 1, 0);
        tree_stack.resize(n + 1, 0);
        root = cnt = top = 0;
        for(int i = n; i >= 1; i--)
            tree_stack[++top] = i;
        
        //tree_deep.resize(n + 1, 0);
    }
};

void solve(){
    int n, d;
    std::cin >> n >> d;
    std::vector<int> k(n + 1, 0);
    std::vector<int> s(n + 1, 0);
    for(int i = 1; i <= n; i++){
        std::cin >> k[i] >> s[i];
    }

    auto scp = Scapegoat<int>((n + d) + 10, k);

    //scp.print_tree(scp.Root());

    std::vector<int> vis(n + 1, false);
    int cnt = 0;
    int ans = 0;
    std::vector<std::vector<int>> time(d + 1);
    for(int i = 1; i <= d; i++){
        int ind = scp.kth(1);

        //std::cerr << "time " << i << ": " << endl;
        //scp.print_tree(scp.Root());

        assert(ind != 0);
        scp.Del();
        if(!vis[ind]){
            vis[ind] = true;
            cnt += 1;
        }

        if(i + s[ind] <= d){
            time[i + s[ind]].push_back(ind);
        }

        std::sort(time[i].begin(), time[i].end(), [&](auto a, auto b){
            return s[a] < s[b];
        });

        for(auto x : time[i]){
            scp.Insert(k[x], x);
        }

        if(cnt == n){
            ans = i;
            break;
        }
    }
    std::cout << (ans == 0 ? -1 : ans) << endl;
}