2020牛客暑期多校训练营（第十场）I-Tournament

题目大意

有n个球队，每个球队都和其它所有球队比一场，所以一共有场比赛，每天一场比赛。
每个球队会在第一场比赛开始时到，最后一场比赛后走。
安排一个日程表，使所有球队停留的天数之和最小。

解题思路

最开始拿到题，由于样例的关系，还以为就是暴力输出全排列即可（发出了WA的声音）。

输入：
4
输出：
1 2
1 3
1 4
2 3
2 4
3 4

但是稍加思索，就会想到这样绝对不是最优安排。
假设我们有10个队，可以看到，我们的确照顾到了1号队，但是他们是比完9场就走了，而2,3,4,...,10号队都要挨个到来，要在场下白费好久。（而且1号队也是要看比赛的呀）

所以，我们要尽量地折中每个队伍的停留时间。
于是一拍脑袋，我们可以把n个队伍分成两半，得到这样的构造方法：

• 前一半互相比赛
• 前一半和后一半比赛
• 后一半互相比赛

详细操作就不赘述了，看代码：

AC代码（主函数）

int main()
{
    int T,n,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=2;i<=n/2;i++)
            for(j=1;j<i;j++)
                printf("%d %d\n",j,i);
        for(i=n/2+1;i<n;i++)
            for(j=1;j<=n-i;j++)
                printf("%d %d\n",j,i);
        for(i=1;i<=n/2;i++)
            for(j=n-i+1;j<=n;j++)
                printf("%d %d\n",i,j);
        for(i=n/2+1;i<n;i++)
            for(j=i+1;j<=n;j++)
                printf("%d %d\n",i,j);                    
    }
}