题解：CF2090C Dining Hall

· · 题解

首先，很容易看出对于每个桌子，左下角的位置一定是四个位置中距离最短的。如果有一张空桌子，只有左下角位置被选掉了，客人才会做到其他位置上。

我先把所有可能用到的左下角的位置丢到一个优先队列 q1 里面备选。排序规则就是按距离排序。

可能用到的位置有哪些呢？容易发现，假设所有人的 t_i 都是 0，x+y 相等的点应该是一条斜线，即从左下到右上依次排布，所以可能用到的行数和列数应该是 \sqrt{2n}。

如果说有一个左下角的位置被占掉了，我就把这张桌上的其他位置丢到另一个优先队列 q2 里备选。

处理客人的时候，如果 t_i=1，就比较 q1 和 q2 堆顶的距离大小，拿小的。如果 t_i=0，就把 q1 的堆顶拿掉。

::::success[代码如下:]

#include<bits/stdc++.h>
using namespace std;
int t, n;
int f[50010];
struct node {
    int x, y;
    bool operator < (const node k) const {
        int dis = x + y + (x % 3 == 2) * (y % 3 == 2) * 2;
        int disk = k.x + k.y + (k.x % 3 == 2) * (k.y % 3 == 2) * 2;
        if(dis != disk) return dis > disk;
        else if(x != k.x) return x > k.x;
        else return y > k.y;
    }
};
priority_queue<node> q1, q2;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t --) {
        cin >> n;
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        for(int i = 1; i <= n; i ++) cin >> f[i];
        for(int i = 0; i <= sqrt(2 * n) + 1; i ++) {
            for(int j = 0; j <= sqrt(2 * n) + 1; j ++) {
                q1.push({3 * i + 1, 3 * j + 1});
            }
        }
        for(int i = 1; i <= n; i ++) {
            if(f[i] == 1) {
                if(q2.empty() || q2.top() < q1.top()) {
                    int x = q1.top().x, y = q1.top().y; q1.pop();
                    cout << x << " " << y << '\n';
                    q2.push({x + 1, y});
                    q2.push({x, y + 1});
                    q2.push({x + 1, y + 1});
                }
                else {
                    int x = q2.top().x, y = q2.top().y; q2.pop();
                    cout << x << " " << y << '\n';
                }
            }
            else {
                int x = q1.top().x, y = q1.top().y; q1.pop();
                cout << x << " " << y << '\n';
                q2.push({x + 1, y});
                q2.push({x, y + 1});
                q2.push({x + 1, y + 1});
            }
        }
    }
    return 0;
}

::::

这个题因为小错误调了很久，纪念一下。

非常感谢 @The_foolishest_OIer 帮我调题！