P11396 排队 题解 & 从部分分做法到正解

· · 题解

更好的阅读体验？

Subtask #1

分类讨论即可。

时间复杂度 O(1)。

Subtask #2

暴力搜索每个猫猫后面要不要放隔板。假设最后一只猫后面一定要放隔板。再进行 O(n) 的判定合法并更新答案。

时间复杂度 O(n2^n)。

Code:

struct node {
    int x, y;
    friend bool operator < (const node &x, const node &y) {
        return x.x == y.x ? x.y < y.y : x.x < y.x;
    }
} b[N];

bool check() {
    for (int i = 1; i <= n; i++) {
        if (q[i] < b[i].y) return 1;
        else if (q[i] > b[i].y) return 0;
    }
    return 0;
}

void subtask2() {
    for (int i = 1; i <= n; i++) q[i] = -1;
    for (int i = 1 << (n - 1); i < (1 << n); i++) {
        int l = 0;
        for (int j = 0; j < n; j++) 
            if (i & (1 << j)) {
                int mn = 1 << 30;
                for (int k = l + 1; k <= j + 1; k++) 
                    mn = min(mn, a[k]);
                for (int k = l + 1; k <= j + 1; k++) 
                    b[k] = {mn, a[k]};
                l = j + 1;
            }
        sort(b + 1, b + n + 1);
        if (check()) 
            for (int j = 1; j <= n; j++) 
                q[j] = b[j].y;
    }
    for (int i = 1; i <= n; i++) 
        printf("%d ", q[i]);
}

Subtask #4

显然 a_k 最小。那么根据题意，应让字典序最大。

你会发现无论怎么分，a_k 总是在第一位。

那么定下了第一位为 a_k，剩下的呢？

应当以 a_k 为连通块的区域进行分第一组。因为由题可知一组组内成员一定在其他组的前面。

那么我们要使第二位尽可能大，应当选择 a_k 左面或右面更大者。可以证明只选左/右面优于左右都选。因为都选的话第二个值就会变成左右最小值了。

因为 a 是 1 \sim n 的一个排列，所以不用担心 a_{k-1}=a_{k+1} 的问题。

选完了第一组，剩下的就全是第二组啦！

也许我的语言并不完善，边看代码边食用更佳。

void subtask4() {
    int k = 0;
    for (int i = 1; i <= n && !k; i++) 
        if (a[i] == 1) 
            k = i; // 找到最小值 a[k]
    if (a[k - 1] > a[k + 1]) { // 找更大的当答案的第二位
        for (int i = k; i; --i) 
            printf("%d ", a[i]); // 根据性质
        for (int i = k + 1; i <= n; i++) 
            printf("%d ", a[i]); // 
    } else {
        for (int i = k; i <= n; i++) 
            printf("%d ", a[i]); // 
        for (int i = k - 1; i; --i) 
            printf("%d ", a[i]); // 
    }
    printf("\n");
}

Subtask #5

可以从 Subtask #4 推广而来。

更一般的，假设当前选了若干组，剩下猫猫的集合为 S。

那么当前 S 内的最小值（记为 x）就是下一个入场的猫猫。

根据 Subtask #4 的结论，我们应选择 x 左面或右面的元素，这取决于哪边的元素更大。

代码实现时，可以用堆或者 set 来维护 S。我们还要记录这个猫猫是否已经在队伍里了。详见代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 50;

int n, a[N], q[N];

set <int> s; // 集合 S，本代码使用 set 实现
int id[N], vis[N];
// id 是这个猫猫的下标，vis 是这个猫猫是否进队

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) id[a[i]] = i;
    for (int i = 1; i <= n; i++) s.insert(a[i]); // 最初所有猫猫都在 S 里
    vis[0] = vis[n + 1] = 1; // 方便后续代码，不用再判边界
    while (!s.empty()) { // 有猫猫没进队
        int x = *s.begin(), y = id[x]; // a[y] 为最小猫猫入场时间
        //cerr << x << " " << y << endl; // 114514
        vis[y] = 1; // 取走啦
        s.erase(x); // 删除啦
        printf("%d ", x); // 进队啦
        if (!vis[y - 1] && !vis[y + 1]) { // 都没有取走呀
            if (a[y - 1] > a[y + 1]) { // 左面的更大捏
                vis[y - 1] = 1; // 取走啦
                s.erase(a[y - 1]); // 删除啦
                printf("%d ", a[y - 1]); // 进队啦
                for (int i = y - 2; i >= 1 && a[i] > a[i + 1] && !vis[i]; i--) {
                    vis[i] = 1;
                    s.erase(a[i]);
                    printf("%d ", a[i]);
                } // 自行理解吧
            } else { // 右面的更大捏
                vis[y + 1] = 1; // 取走啦
                s.erase(a[y + 1]); // 删除啦
                printf("%d ", a[y + 1]); // 进队啦
                for (int i = y + 2; i <= n && a[i] > a[i - 1] && !vis[i]; i++) {
                    vis[i] = 1;
                    s.erase(a[i]);
                    printf("%d ", a[i]);
                } // 自行理解吧  
            }
        } else if (!vis[y - 1]) { // 只有左面有猫猫
            vis[y - 1] = 1; // 取走啦
            s.erase(a[y - 1]); // 删除啦
            printf("%d ", a[y - 1]); // 进队啦
            for (int i = y - 2; i >= 1 && a[i] > a[i + 1] && !vis[i]; i--) {
                vis[i] = 1;
                s.erase(a[i]);
                printf("%d ", a[i]);
            } // 自行理解吧  
        } else if (!vis[y + 1]) { // 只有右面有猫猫
            vis[y + 1] = 1; // 取走啦
            s.erase(a[y + 1]); // 删除啦
            printf("%d ", a[y + 1]); // 进队啦
            for (int i = y + 2; i <= n && a[i] > a[i - 1] && !vis[i]; i++) {
                vis[i] = 1;
                s.erase(a[i]);
                printf("%d ", a[i]);
            } // 自行理解吧  
        }
    }
    return 0;
}

看我写了这么多，留下个赞不过分吧……