题解：P16354 「Diligent-OI R3 B」天际线

· · 题解

省流：题二是绿，赛时调了好久没过去，赛后发题解来纪念一下，心态极炸。

思路点拨：

题外话：这个题目是较有思维难度的，可以发现近几个月的洛谷月赛考的这种逻辑思维题目还是很多的，个人认为还是相当不错的，所以做不出来我想大家也不用气馁，加油。

回归正题，题目要求我们要输出一种合法的排列，来满足题目中的看见的方式，特别注意，这里的南可以理解成左边，北则可以理解成右边，这样就是一个线性的处理，更加直观了。

聪明的你一定可以看出，从右向左看一定有第一个右可见点，那我们可不可以从这个点入手去解决呢，可以！

正解就是这个，我们不难发现，找到这个点的坐标就可以将整个线性数组两个部分，左部分与右部分，下面将分别处理。

左部分的处理方式：

这个相对来说是很简单的，由于题目说字典序要尽可能小，所以我们从 1 开始，一直按顺序排列到最高点的那个位置即可。

右部分的处理方式：

这里为了满足题目要求，可以分成两种情况：

  1. 给右可见的位置，从大到小填数。
  2. 给右不可见的位置，从小到大填剩下的数。

这就是两种右部分的逻辑。

c_i=1 的处理方式：

其实按照我们以前的逻辑，一定是会出现问题的，因为他还有类似凹槽的情况，那也别着急，因为我们从左往右元素到最高点位置总满足单调递增，所以我给他的左边位置互换不久可以了。

无解的处理方式：

其实本题无解的方式是最简单的，这里分三步：

  2. 如果某一个位置 c_i=1 且与此同时对应位置的 a_i 或 b_i 为 1 时，也无解。
  3. 如果最后一个左可见位置比第一个右可见位置小，无解。

然后这道题就完事了，还是挺难的，但是分析下来还是很有成就感的。

ACCode:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;// 开到这么多足够了
char a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];

void solve(int n) {// 打包成solve函数更方便些吧我感觉
    memset(ans, 0, sizeof(ans));// 将数组中所有元素都设置为0
    cin >> a >> b >> c;
    bool flag = 1;// 判断无解的那个变量
    for (int i = 0; i < n; i++) {
        if (c[i] == '1') {
            if (i == 0 || i == n - 1) flag = 0;// 判断无解1
            if (a[i] == '1' || b[i] == '1') flag = 0;// 判断无解2
        }
    }
    int maxx = 0;
    int minn = n + 1;
    for (int i = 0; i < n; i++) {// 找最后的左边界
        if (a[i] == '1') maxx = max(maxx, i + 1);
    }
    for (int i = 0; i < n; i++) {// 找最开始的右边界
        if (b[i] == '1') {
            minn = min(minn, i + 1);
        }
    }
    if (maxx > minn) flag = 0;// 判断无解3
    if (!flag) {
        cout << "-1\n";
        return;
    }
    int mid = minn;// 以第一个右边界为临界点
    for (int i = 1; i < mid; i++) ans[i] = i;
    for (int i = mid - 1; i >= 1; i--) {
        if (c[i - 1] == '1') {
            swap(ans[i], ans[i - 1]);
        }// 出现凹槽就转换
    }

    int l = mid, r = n;
    for (int i = mid; i <= n; i++) {// r就是从大到小的那个
        if (b[i - 1] == '1') ans[i] = r--;
    }
    for (int i = mid; i <= n; i++) {// l就是从小到大的那个
        if (b[i - 1] == '0') ans[i] = l++;
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        solve(n);
    }
    return 0;
}