2017年湖南省第十三届大学生计算机程序设计竞赛Seating Arrangement

痛定思痛。 2022-06-08 00:28 193阅读 0赞

## Description ##

Mr. Teacher老师班上一共有*n*个同学，编号为1到*n*。 在上课的时候Mr. Teacher要求同学们从左至右按1, 2, …, *n*的顺序坐成一排，这样每个同学的位置是固定的，谁没来上课就一目了然了。

但是时间长了之后，Mr. Teacher发现坐得离得远的同学往往因为交流很少而逐渐变得生疏了，于是他决定重新安排同学们的座位，并且在新的座位安排中，任意两个相邻的同学的编号之差的绝对值都必须大于*d*。

现在Mr. Teacher需要你帮忙给出一个座位安排方案。

## Input ##

输入包含不超过100组数据。 每组数据包含两个整数*n*, *d*(4 ≤ *n* ≤ 100, 1 ≤ *d* ≤ *n* − 2)。

## Output ##

对于每组数据，用一行输出一个可行的座位安排方案，相邻两个数之间用一个空格隔开。 座位安排方案由*n*个1到*n*的数组成，从左到右依次描述了各个座位安排给了哪个编号的同学。 如果有多种可行的座位安排方案，输出任意一种即可。 如果不存在满足要求的座位安排方案，则输出“-1”。

## Sample Input ##

6 1
    6 3
    7 2

## Sample Output ##

2 4 6 1 3 5
    -1
    1 4 7 3 6 2 5

## Hint ##

对于第一个样例，存在多种可行的方案，如1 3 5 2 4 6，2 5 1 4 6 3，4 6 3 1 5 2等，输出任意一个可行方案即可。

对于第三个样例，同样存在多种可行方案，输出任意一个可行方案即可。

\#include<cstring>  
\#include<cmath>  
\#include<cstdio>  
\#include<vector>  
\#include<algorithm>  
using namespace std;  
struct A  
\{  
    int a\[101\];  
    int s,e,len;  
\} f\[101\];  
bool cmp(A x,A y)  
\{  
    return x.e>y.e;  
\}  
int main()  
\{  
    int l,n,d,j;  
    while(~scanf("%d %d",&n,&d))  
    \{  
        d++;  
        for(int i=1; i<=d; i++)  
        \{  
            l=0;  
            for(j=i; j<=n; j+=d)  
            \{  
                f\[i\].a\[l++\]=j;  
            \}  
            f\[i\].len=l;  
            f\[i\].s=f\[i\].a\[0\];  
            f\[i\].e=f\[i\].a\[l-1\];  
        \}  
        sort(f+1,f+d+1,cmp);  
//        for(int i=1;i<=d;i++)  
//        \{  
//            printf("%d %d\\n",f\[i\].s,f\[i\].e);  
//        \}  
        int ok=0;  
        int temp=f\[1\].e;  
        for(int i=2; i<=d; i++)  
        \{  
            if(abs(temp-f\[i\].s)>d)  
                temp=f\[i\].e;  
            else  
            \{  
                ok=1;  
                break;  
            \}  
        \}  
        if(ok)  
        \{  
            printf("-1\\n");  
            continue;  
        \}  
        for(int i=1; i<=d; i++)  
        \{  
            for(j=0; j<f\[i\].len; j++)  
            \{  
                if(i==d&&j==f\[i\].len-1)  
                    printf("%d\\n",f\[i\].a\[j\]);  
                else  
                    printf("%d ",f\[i\].a\[j\]);  
            \}  
        \}  
    \}  
    return 0;  
\}