Problem K: 勇气是人类的赞歌

📝 题目描述

🔑 算法模块

💡 思路分析

题中给出的数组其实是一个前缀和数组，从给出的数组中，我们拆一下前缀和，可以知道每个元素对 \(3\) 取余的模数，我们可以先整理一下 \(1-n\) 的数字，分为除三余零、除三余一、除三余二，然后遍历给每个位置上分数字。如果轮到某个位置上时，应该放的种类里面没有剩下的，就输出 \(-1\)。

🖥️ 代码实现

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a, b(n);
    std::vector<std::vector<int>> c(3);
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
        c[(i + 1) % 3].push_back(i + 1);
    }
    int x = 0;
    for (int i = 0; i < n; i++) {
        x = (b[i] + 3 - x) % 3;
        if (!c[x].size()) {
            std::cout << -1 << "\n";
            return 0;
        }
        a.push_back(c[x].back());
        c[x].pop_back();
        x = b[i];
    }
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
    return 0;
}

⏱️ 复杂度分析

📚 拓展