P3566 [POI2014] KLO-Bricks 题解

· · 题解

P3566 [POI2014] KLO-Bricks 题解

大致意思：

现在有 n 种颜色的砖块，第一个必须放第 p 种颜色，最后一定得放第 q 种颜色，剩余中间的需要自己构造，使得每相邻两个砖块的颜色不相等，有解随便输出任意一种，无解则输出 0。

大致思路：

这是一道很好的贪心构造题，最优的方案，肯定就是先放最少最多，用最多的来分隔少的，因为这样最多的可以放置的更为均匀，以达到我们实现最优方案的目的，不然会导致多的前面放的过少，后面聚在一堆，实现出来的代码显示的是无解。当然如果当前最多的颜色与前面一项相等，那么我们要取一二大的，以此类推。

而我们知道了，想要实现此方法需要一边运行放颜色，一边排序，如果直接用用排序函数，占用时间太大，肯定会超时，那么我们就可以用到优先队列，它是可以边运行边排序的。

我们可以用变量 s，记录总砖块数，接着通过循环实现放砖块：

当然，在过程中我们还要判断，本种砖块数是否大于 0，和此时队列里还有没有砖块，如果没有砖块，则无解。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,p,y,s;
int ar[1000005];
bool f;
struct node{
    int x;
    int id;
}a[1000005];
bool operator <(node l,node r){
    if (l.x != r.x) return l.x<r.x;
    if (l.id == y) return 0;
    if (r.id == y) return 1;
    return 0; 
}
priority_queue<node> q;

int main(){
    cin>>n>>p>>y;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
        if(i==p) a[i].x--;
        if(i==y) a[i].x--;
        s+=a[i].x;
        a[i].id=i;
        q.push(node{a[i].x,i});
    }

    int u=p;
    ar[s+2]=y;
    for(int i=2;i<=s+1;i++){
        node t=q.top();q.pop();
        if(t.x>0) t=t;
        else{
            f=1;
            break;
        }
        if(t.id!=u&&t.x>0){
            ar[i]=t.id;
            q.push(node{t.x-1,t.id});
            u=ar[i];
        }else if(q.size()&&t.x>0){
            node v=q.top();
            q.pop();
            ar[i]=v.id;
            q.push(node{v.x-1,v.id});
            q.push(node{t.x,t.id});
            u=ar[i];
        }else if(!q.size()){
            f=1;
            break;//不加 RE，我找了两位大佬才调出来
        }
    }
    if(f){
        cout<<"0";
        return 0;
    }
    for(int i=1;i<=s+1;i++){
        if(ar[i]==ar[i+1]){
            f=1;
        }
    }
    if(f){
        cout<<"0";
        return 0;
    }
    cout<<p<<" ";
    for(int i=2;i<=s+1;i++){
        cout<<ar[i]<<" ";
    }
    cout<<ar[s+2];
    return 0;
}

这样这道题就结束啦！