题解 P3566 【[POI2014]KLO-Bricks】

· · 题解

快CPS了， 一个一般学校的一般Oier很虚，感觉自己很菜， 好不容易写拉一道好的贪心题（写了好长时间啊），要发个题解。

这题见过好多遍了，也有好多人讲过， 自己认为很好写，然后一直没写，一些才发现原来有一点不好写（是我的代码能力太差了。。）

本题是一个练习代码能力和细节处理的好题

进入正题

1.贪心策略 ：在保证相邻两个颜色不同时，先放多的，若一样多，则放与末尾颜色相同的。（正确性感性理解一下）

变量

int k, s, t, n, pre;//k为颜色数，s为第一个块颜色，t为最后一个块的颜色， n为总块数， pre为前一个快的颜色;
int ans[maxn];//记录答案;
bool flag;//代码中会解释用途;

struct Node{
    int col, id;//这个结构体没啥用，可以用一个变量代替。。;
}a[maxn];

处理 一样多的 且 一样多的中有与末尾颜色一样的 

struct note{
    int now, w;//now颜色， w个数;
    friend bool operator < (note a, note b){
        if (a.w != b.w) return a.w < b.w; //大根堆应为小于号
        if (a.now == t) return false;//t为末尾颜色
        return true;
    }
};

priority_queue<note>Q;

快读

int f_;
char ch_;
template <class T>
    inline T read (T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ > '9' || ch_ < '0'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_*f_;
    }

激动人心的时候（这么长时间，终于有代码啦）

code 
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int maxn = 1e6 + 10;

int k, s, t, n, cnt, pre;
int ans[maxn];
bool flag;

struct Node{
    int col, id;
}a[maxn];

struct note{
    int now, w;
    friend bool operator < (note a, note b){
        if (a.w != b.w) return a.w < b.w;
        if (a.now == t) return false;
        return true;
    }
};

priority_queue<note>Q;

int f_;
char ch_;
template <class T>
    inline T read (T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ > '9' || ch_ < '0'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_*f_;
    }

int main(){
    read(k);
    read(s);
    read(t);
    for (register int i = 1;i <= k; ++i){
        read(a[i].col);
        a[i].id = i;
        n += a[i].col;
        if (a[i].id == s) a[i].col--;
        if (a[i].id == t) a[i].col--;
        if (a[i].col < 0) {printf("0"); return 0;}//题意要求，因为Bitie could have made a mistake，所以他会当块数没有他记忆中的多， 则跳出;
        Q.push((note){i, a[i].col}); 
    }
    pre = s;//从第二个块开始，前一个块为s;
    ans[1] = s;
    ans[n] = t; 
    note top, tmp;
    for (register int i = 2;i < n; ++i){
        top = Q.top();
        Q.pop();
        flag = false;
        if (top.now == pre){//这里是重点，若与前一个颜色相同则用tmp记录堆顶
            flag = true;
            tmp = top;
            if (!Q.empty()) 
                top = Q.top();//若第二堆顶有则放它，否则就会把两个一样的放在一起，然后跳出即可
            else {
                printf("0"); 
                return 0;
            }
            Q.pop();
        }
        pre = ans[i] = top.now;
        if (top.w > 1) 
            Q.push((note){top.now, top.w - 1});
        if (flag) 
            Q.push(tmp);//若flag为一，则把原来堆顶放回去
    }
    if (ans[n-1] == ans[n]) {
        printf("0"); 
        return 0;
    }
    for (register int i = 1;i <= n; ++i){
        if (i != n)
            printf("%d ",ans[i]);
        else printf("%d", ans[i]);
    }
    return 0;
}

最后记住pus("0")不行，因为它自带换行，因为忘记啦， 所以提交时60pt好几次

最后祝大家oi路上越走越顺

AK ioi

日拱一卒，功不唐捐！！！