合唱队形2 洛谷U5874

题目背景

上次老师挑出来的（N-K）位同学很不高兴，于是他们准备自己组建合唱队形。他们请了kkk来帮忙。

题目描述

他们安排了一个动作——手拉着手唱一首歌（就是他们围成一个圈）。如果有两个相邻的同学的身高差非常大（比如姚明和一个1.5米高的人站在一起）的话，评委会感觉非常不爽。于是kkk需要帮助他们求出一种排队方案，使他们身高差距最大值最小，并输出这个最小值和这个方案。

输入输出格式

输入格式：

第一行一个整数N表示有N个人（排成一个圈）

第二行N个整数表示每个人的身高

输出格式：

第一行一个整数表示最小的身高差距最大值

第二行N个整数表示这个最优方案，如果多解输出字典序最小

输入输出样例

输入样例#1：

6

1 2 3 4 5 6

输出样例#1：

2

1,2,4,6,5,3

说明

1<=N<=6000

1<=身高<=1000

思路：

　　先把身高排序

　　然后我们就用一个很神奇的环来得出答案

　　把1作为环的一个点

　　2~n的元素如果第i个元素的i%2==1放到右边

　　否则放到左边成为一个环

　　然后判断哪两个之间的身高差最大

　　这样就能得出来第一问的答案

　　现在就是要解决字典序的问题了

　　把排序后的身高进行编环

　　还是把最矮的放到第一位

　　然后如果第i+1个元素-第i个元素>ans

　　就把第i个元素放到第最左端

　　否则放到最右端

　　完成后左右两端链接成为环

　　从最矮的往后输出就是答案

来，上代码：

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

struct node {

    int now,dis;

};

struct node ai[],loop[];

int n,maxn,minn,num=,ans=;

bool if_in[];

bool cmp(struct node SOME_1,struct node SOME_2){return SOME_1.dis<SOME_2.dis;}

void sort_1()

{

    int now_1=,now_2=n,now_3=,cur_1=ai[].dis;

    loop[]=ai[now_3++];

    while(now_3<=n)

    {

        if(now_3==n) loop[++now_1]=ai[now_3++];

        else

        {

            if(ai[now_3+].dis-cur_1<=ans)

            {

                loop[++now_1]=ai[now_3++];

            }

            else

            {

                cur_1=ai[now_3].dis;

                loop[now_2--]=ai[now_3++];

            }

        }

    }

    int v=,cnm[],now_4=;

    for(int i=v;i<=n;i++) cnm[++now_4]=loop[i].dis;

    for(int i=;i<v;i++) cnm[++now_4]=loop[i].dis;

    for(int i=;i<n;i++) printf("%d,",cnm[i]);

    printf("%d\n",cnm[n]);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        ai[i].now=i;

        scanf("%d",&ai[i].dis);

    }

    sort(ai+,ai+n+,cmp);

    loop[++num]=ai[];

    for(int i=;i<=n;i++) if(i%==) loop[++num]=ai[i];

    for(int i=n;i>=;i--) if(i%==) loop[++num]=ai[i];

    for(int i=;i<n;i++) ans=max(ans,abs(loop[i].dis-loop[i+].dis));

    ans=max(ans,abs(loop[n].dis-loop[].dis));

    printf("%d\n",ans);

    sort_1();

    return ;

}

巴特西

合唱队形2 洛谷U5874

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章