必威体育Betway必威体育官网
当前位置:首页 > IT技术

团子最大家族(clannad)

时间:2019-08-12 12:39:59来源:IT技术作者:seo实验室小编阅读:82次「手机版」
 

だんご大家族

团子最大家族(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 阅读(...) 评论(...) 编辑 收藏

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读