「POI2014 R1」砖块 Bricks 题解

题目大意

给定 k 种颜色的砖块，每种颜色有特定数量。已知原始砖块序列的第一个颜色是 p，最后一个颜色是 q，且任意相邻两个砖块颜色不同。要求构造一个满足条件的序列，或者判断无解。

解题思路

这是一个典型的构造问题，需要合理安排砖块的排列顺序，使得：

1. 第一个砖块颜色为 p
2. 最后一个砖块颜色为 q
3. 相邻砖块颜色不同
4. 每种颜色的砖块数量符合要求

关键观察

1. 可行性判断：

   • 如果某种颜色的砖块数量过多（超过总数的一半+1），则无解
   • 如果首尾颜色相同但数量只有1个，则无解（因为需要放在首尾两个位置）

2. 构造策略：

   • 使用贪心+优先队列，每次选择剩余数量最多的颜色（且不与前一个颜色相同）
   • 如果必须选择与前一颜色相同的颜色，则说明无解

算法流程

1. 预处理：

   • 将首尾颜色对应的砖块数量各减1
   • 如果减后出现负数，则无解（特殊情况：k=1时允许首尾相同）

2. 贪心构造：

   • 使用大根堆维护各种颜色的剩余数量
   • 每次选择剩余数量最多的颜色（且不与前一个颜色相同）
   • 如果堆顶颜色与前一个相同，则选择次多的颜色
   • 如果无法选择不同的颜色，则无解

3. 收尾处理：

   • 在序列末尾添加最后一个颜色 q
   • 检查整个序列是否满足相邻不同的条件

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 1e6 + 5;

int k, p, q;
int a[N];

struct node {
    int num, clo;
};
struct cmp {
    bool operator()(node x, node y) {
        return x.num < y.num;
    }
};
priority_queue<node, vector<node>, cmp> Q;

vector<int> ans;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    bool flag = 1;
    int sum = 0;

    cin >> k >> p >> q;

    for (int i = 1; i <= k; ++i) {
        cin >> a[i];
        sum += a[i];

        if (i == q)
            --a[i];

        if (i == p)
            --a[i];

        if (a[i] > 0)
            Q.push({a[i], i});
    }

    // 检查首尾颜色数量是否足够
    if (a[q] < 0 && k != 1) {
        cout << "0";
        return 0;
    }

    // 初始放置第一个颜色 p
    ans.push_back(p);
    int last = p;

    while (!Q.empty()) {
        bool f = 0;
        node x = Q.top();
        Q.pop();

        // 确保取出的数据是最新的
        while (!Q.empty() && x.num != a[x.clo]) {
            x = Q.top();
            Q.pop();
        }

        node y;

        // 如果堆顶颜色与上一个相同，需要选择次多的颜色
        if (x.clo == last) {
            y = x;

            if (Q.empty()) {
                flag = 0;
                break;
            }

            f = 1;
            x = Q.top();
            Q.pop();

            while (!Q.empty() && x.num != a[x.clo]) {
                x = Q.top();
                Q.pop();
            }
        }

        // 如果当前颜色不是q且数量等于a[q]，优先放置q
        if (x.clo != q && x.num == a[q] && q != last) {
            ans.push_back(q);
            last = q;
            a[q]--;
            Q.push(x);

            if (a[q])
                Q.push({a[q], q});
        } else {
            ans.push_back(x.clo);
            last = x.clo;
            x.num--;
            a[x.clo]--;

            if (x.num)
                Q.push(x);
        }

        if (f)
            Q.push(y);
    }

    // 在序列末尾添加最后一个颜色 q
    if (ans.size() < sum)
        ans.push_back(q);

    // 检查相邻颜色是否相同
    for (int i = 0; i < ans.size() - 1; ++i)
        if (ans[i] == ans[i + 1])
            flag = 0;

    if (!flag) {
        cout << "0";
        return 0;
    }

    // 输出结果
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i];
        if (i != ans.size() - 1)
            cout << " ";
    }

    return 0;
}

算法分析

时间复杂度

• 每个元素最多入队出队一次
• 时间复杂度：O(n log k)，其中 n 是砖块总数，k 是颜色种类数
• 使用优先队列维护，每次操作 O(log k)

空间复杂度

• O(n + k)，存储序列和优先队列

样例分析

样例1

输入：3 3 1
      2 3 3
输出：3 2 1 3 2 3 2 1

解释：颜色1有2个，颜色2有3个，颜色3有3个。首颜色为3，尾颜色为1。输出序列满足所有条件。

样例2

输入：3 3 1
      2 4 2
输出：0

解释：颜色2有4个，但总数为8，4 > (8+1)/2 = 4.5，数量过多导致无解。

总结

本题的关键在于：

1. 贪心策略：优先选择剩余数量最多的颜色
2. 可行性判断：检查颜色数量是否过多
3. 边界处理：正确处理首尾颜色的特殊情况

这种贪心+优先队列的方法能够高效地构造出满足条件的序列，或者在无法构造时及时判断无解。