牛客contest5675-I

传送门

题目大意

有n个球队，每个球队都和其它所有球队比一场，即一共有

场比赛，每天只有一场比赛。
每个球队会在第一场比赛开始时到，最后一场比赛后走。请安排一个日程表，使所有球队停留的天数之和最小。输出这个日程表。

思路

样例害人啊，出题人编了一个长得很像全排列的样例…

其实仔细一想会发现全排列不仅不是通解，而且大多数情况下都不是答案。当队伍多起来时，全排列会优先满足第一个队伍，这时候其他队伍只能一个一个挨着上场，浪费了大量的等待时间。

所以最优的方案可能会是一种“折中”的方案，即不去强调每一个队的最优。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0X7F7F7F7F;

int t, n;

int main()
{
	cin >> t;
	while(t--)
	{
		cin >> n;		
		for(int i = 2; i <= n/2; i++)
			for(int j = 1; j < i; j++)
				printf("%d %d\n", j, i);
		for(int i = n/2+1; i < n; i++)
			for(int j = 1; j <= n-i; j++)
				printf("%d %d\n", j, i);
				
		for(int i = 1; i <= n/2; i++)
			for(int j = n-i+1; j <= n; j++)
				printf("%d %d\n", i, j);
		for(int i = n/2+1; i < n; i++)
			for(int j = i+1; j <= n; j++)
				printf("%d %d\n", i, j);
	}
	
	return 0;
} 

参考文章： https://blog.nowcoder.net/n/823f0f139c9b4200b090385da2380fd1