「だんご大家族」团子最大家族（clannad）

だんご大家族

团子最大家族（clannad）

题目描述

bx2k有许多五颜六色的萌萌哒团子。每个团子有一种颜色。

他决定将m个团子排成一排。为了美观，他要求任何相邻的两个团子不能有相同的颜色。

因为bx2k很懒，因此他来寻求你的帮助。

输入

输入文件包含两行。

第一行为一个整数n，表示共有n种颜色的团子。

第二行为n个空格隔开的整数ai，表示颜色为i的团子有ai个。题目中的m=n∑i=1aim=∑i=1nai

输出

输出文件包含一行，m个空格隔开的整数，表示你给出的方案。如果有多种方案，输出任意一种即可。如果不存在合法方案，输出-1。

样例输入

样例输入1
3
2 3 3
样例输入2
1
2

样例输出

样例输出1
1 2 3 2 3 2 3 1
样例输出2
-1

提示

数据规模与约定

本题有10个测试点，每个测试点占10%的分数。

对于100%数据，时间限制为1s，空间限制为256MB。

对于20%的数据，n≤5，m≤10。

对于50%的数据，n≤1000，m≤1000。

另外20%的数据，n≤20，m≤100000。

对于100%的数据，1≤n≤100000,1≤m≤100000,1≤ai≤m。

来源

南外模拟卷

好水。。但我想了好久

只要把每一个扔进大跟堆里，每次取堆顶的两个，然后再放回

效率O（mlogn）

#include<cstdio>
#include<iOStream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 100005
using namespace std;
int n,s[maxn],Max,ans[maxn],top,num;
struct node{
    int num,co;
    bool operator<(const node &T)const{
        return T.num>num;
    }
}t;
priority_queue<node>q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        Max=max(Max,s[i]);num+=s[i];
        t.num=s[i];t.co=i;
        q.push(t);
    }
    if(Max>num/2){puts("-1");return 0;}
    while(!q.empty()){
        node x=q.top();q.pop();
        if(q.empty()){ans[++top]=x.co;break;}
        node y=q.top();q.pop();
        x.num--;y.num--;
        if(ans[top]==x.co)ans[++top]=y.co,ans[++top]=x.co;
        else ans[++top]=x.co,ans[++top]=y.co;
        if(x.num)q.push(x);
        if(y.num)q.push(y);
    }
    cout<<ans[1];
    for(int i=2;i<=top;i++)printf(" %d",ans[i]);
    cout<<endl;
    return 0;
}

posted @ 2018-09-23 16:03 liankewei 阅读(...) 评论(...) 编辑收藏

团子最大家族（clannad）