[POI 21 Stage 1] Bricks

作法：

首先先把第一個和最後一個方塊放好，如果沒有限制最後一個和最後第二個的方塊要不同色，那大概可以想到就只要從左邊到右邊一個一個選，每次選目前剩下的方塊數最多的顏色放就好了(當然不能跟前一個方塊的顏色一樣)，而這件事可以用一個 priority_queue 作，如果 queue 頂端的顏色的方塊已經沒了那就是無解。那至於要怎麼避免最後第二個方塊和最後一個方塊一樣，假設最後一個方塊的顏色是 ed 好了，我是把顏色為 ed 的方塊在 priority_queue 裡面的優先級設成比較高（ 方塊剩餘個數越多的越早出隊，同樣的時候顏色為ed的最晚出隊。 ），這樣就可以盡量避免最後一個方塊放了顏色為 ed 的方塊。最後還要注意到一些特例，例如起點和終點顏色一樣的情形，還有只有一個方塊的情形。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int n,k,st,ed ;
int rk[maxn] ;
struct P
{
    int id,num ;
    bool operator < (const P &rhs) const
    {
        if(num!=rhs.num) return num<rhs.num ;
        return rk[id]>rk[rhs.id] ; /// rk[ed]=1
    }
};
 
int num[maxn] ;
priority_queue<P> pq ;
int ans[maxn] ;
 
bool solve()
{
    if(!num[st] || !num[ed]) return 0 ;
    if(n==1 && st==ed && num[st]==1) { ans[1]=st ; return 1 ; }
    if(st==ed && num[st]==1) return 0 ;
    num[st]-- ; num[ed]-- ;
 
    for(int i=1;i<=k;i++) if(i!=st && num[i]) pq.push((P){i,num[i]}) ;
 
    ans[1]=st ; ans[n]=ed ;
    for(int i=2,now=st;i<=n-1;i++)
    {
        if(pq.empty()) return 0 ;
        P u=pq.top() ; pq.pop() ;
        ans[i]=u.id ;
        num[u.id]-- ;
        if(num[now]) pq.push((P){now,num[now]}) ;
        now=u.id ;
    }
    if(ans[n-1]==ed) return 0 ;
    return 1 ;
}
 
main()
{
    scanf("%d%d%d",&k,&st,&ed) ;
    for(int i=1;i<=k;i++) scanf("%d",&num[i]) , n+=num[i] ;
    rk[ed]=1 ;
    for(int i=1,j=2;i<=k;i++) if(i!=ed) rk[i]=j++ ;
 
    if(!solve()) printf("0\n") ;
    else for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ') ;
}