题解 | #小红的排列构造②#

分析

非常好的构造题

这是题目的核心要求

可以做如下考虑

• 如果当前是, 那么直接按照顺序输出, 构成排列
• 如果当前是, 找到下一个的位置, 并且交换

为什么这么操作?

假设当前位置是是, 下一个位置是, 对于前交换不会影响是否构成排列, 但是交换后因为引入了, 不构成排列了

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10, MOD = 998244353;
const LL INF = 1e18;

int n;
string s;
vector<int> vec;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> s;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i]) vec.push_back(i + 1);
    }

    vector<int> ans(n + 1);
    for (int i = 1; i <= n; ++i) ans[i] = i;

    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '0') {
            int j = upper_bound(vec.begin(), vec.end(), i) - vec.begin();
            if (j >= vec.size()) {
                cout << -1 << '\n';
                return 0;
            }
            swap(ans[i], ans[vec[j]]);
        }
    }

    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}