欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POI2014 Bricks

程序员文章站 2022-03-06 22:20:00
...

Bricks

POI2014
一开始分类讨论半天,wa的一塌糊涂,仔细想想可以贪心哇

题意

1.有n种颜色的砖块
2.第i种颜色的砖块有a[i]个(a[i]>0)
3.把他们放成一排,使得相邻两个砖块的颜色不相同,限定第一个砖块的颜色是start,最后一个砖块的颜色是end
4.请构造出一种合法的方案或判断无解。

1.为了达到“相邻两个砖块的颜色不相同”的目的,当然是多种颜色交替使用了。

2.每次选择剩余数目最多且不与上次重复的砖块

3.但是要防止end砖块被留到最后,我们在数目相同时优先选end颜色的

4.最后判断是否有砖块剩余

5.再判断col[n],col[n-1]颜色是否相同
(因为你只保证col[i]!=col[i-1])

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=1000005;
#define fi first
#define se second
typedef pair<int,int>P;
priority_queue<P>Q;
int n,st,ed;
int cnt[M],sum,ans[M];
int main() {
    scanf("%d %d %d",&n,&st,&ed);
    for(int i=1; i<=n; i++) {
        scanf("%d",&cnt[i]);
        sum+=cnt[i];
    }
    ans[1]=(st==ed?M:st),ans[sum]=M;
    if(n==1&&sum==1){
        printf("1\n");
        return 0;
    }
    cnt[st]--,cnt[ed]--;
    if(n==1||cnt[st]<0||cnt[ed]<0) {
        printf("0\n");
        return 0;
    }
    for(int i=1; i<=n; i++) {
        if(cnt[i]){
            if(i==ed)Q.push(P(cnt[i],M));
            else Q.push(P(cnt[i],i));
        }
    }
    bool flag=1;
    int ls=(st==ed?M:st);
    int now=2;
    while(!Q.empty()) {
        P p1=Q.top();
        Q.pop();
        if(p1.se==ls) {
            if(Q.empty()) {
                flag=0;
                break;
            }
            P p2=Q.top();
            Q.pop();
            p2.fi--;
            ans[now]=p2.se;
            ls=p2.se;
            if(p2.fi)Q.push(p2);
            Q.push(p1);
        } else {
            p1.fi--;
            ans[now]=p1.se;
            ls=p1.se;
            if(p1.fi)Q.push(p1);
        }
        now++;
    }
    if(!flag||ans[sum]==ans[sum-1])printf("0\n");
    else {
        for(int i=1; i<=sum; i++){
            printf("%d ",ans[i]==M?ed:ans[i]);
        }
    }
    return 0;
}
相关标签: POI