你所在的年級有5個班，每班一支球隊在同一塊場地上進行單循環賽, 共要進行10場比賽. 如何安排賽程使對各隊來說都盡量公平呢. 下面是隨便安排的一個賽程: 記5支球隊為A, B, C, D, E，在下表左半部分的右上三角的10個空格中, 隨手填上1,2,10, 就得到一個賽程, 即第1場A對B, 第2場B對C, , 第10場C對E. 為方便起見將這些數字沿對角線對稱地填入左下三角.
這個賽程的公平性如何呢, 不妨只看看各隊每兩場比賽中間得到的休整時間是否均等. 表的右半部分是各隊每兩場比賽間相隔的場次數, 顯然這個賽程對A, E有利, 對D則不公平.

從上面的例子出發討論以下問題:
1)對于5支球隊的比賽, 給出一個各隊每兩場比賽中間都至少相隔一場的賽程.
2)當n支球隊比賽時, 各隊每兩場比賽中間相隔的場次數的上限是多少.
3)在達到2) 的上限的條件下, 給出n=8, n=9的賽程, 并說明它們的編制過程.

問題一

問題二

偶數個球隊:各隊每兩場比賽中間相隔的場次數的最小值的上限是$\frac{n}{2}?1$
奇數個球隊:各隊每兩場比賽中間相隔的場次數的最小值的上限是$\frac{n?3}{2}$
向下取整后，不分奇偶，都是$\frac{n?3}{2}$
式子來源:$R\le (n?3)/2$, $R$為間隔

問題三

編制過程:(暫不給予說明)

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 20;
int n,r,nx,mr;
vector<pair<int,int> >v(200);
vector<int>chose(200);//選擇
int interval[N];//間隔
int ans[N][N];//答案矩陣//優化結構
map<pair<int,int>,int>mv;//對局->選擇
int maxn[N];//當前球隊比賽場次最大值(球隊上次比賽的場次)void f(int);
inline void print_ans();int main(){ // n=12 運行時間突變cin >> n; // n個球隊r = (n-3)/2;//間隔下線（下限）nx = (n-1)*n/2;//(n-1)+(n-2)+...+1//step1. 列出每一個對局(小數在前),并初始化對局int x = 1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){v[x++] = make_pair(i,j);mv[{i,j}]=x-1;}}for(int i=1;i<=n;i++){interval[i] = -1;maxn[i] = -1;}//step2. 初始化選擇if(n%2==0){mr = r+3;//間隔上限int k = 1;//12 34 ... n-1 nfor(int i=1;i<=n-1;i+=2){ans[i][i+1] = ans[i+1][i] = (i+1)/2;maxn[i]=maxn[i+1] = k;chose[k++]=mv[{i,i+1}];}for(int i=1;i<=n-5;i+=4){for(int j=0;j<2;j++){//ans[i+j][i+j+2] = ans[i+j+2][i+j] = k;ans[i+j][(i+j+2+n)%n] = ans[(i+j+2+n)%n][i+j] = k;maxn[i+j]=maxn[(i+j+2+n)%n] = k;chose[k++]=mv[{i+j,(i+j+2+n)%n}];}}f(k);}else{mr = r+2;//間隔上限int k = 1;//12 34 ... n-2 n-1for(int i=1;i<=n-2;i+=2){ans[i][i+1] = ans[i+1][i] = (i+1)/2;maxn[i]=maxn[i+1] = k;chose[k++]=mv[{i,i+1}];}f(k);}//print_ans();return 0;
}
bool flag = false;
void f(int x){if(flag || x == nx+1){if(!flag)print_ans();flag = true;//all return//cout ansreturn ;}//step3. 算間隔,取出必選(可選)的列表（對局列表）vector<int>must_chose;
#if 0for(int i=1;i<=r+1;i++){// x x-1 x-2 .. x-rpair<int,int> pi_t = v[chose[x-i]];interval[pi_t.first] = interval[pi_t.second] = i;}
#endifbool m_or_ke = false;//false 表示 是可選列表， 反之是必選vector<int>must_n;vector<int>no_n;for(int i=1;i<=n;i++){if(maxn[i]==-1){//沒被選過must_n.push_back(i);continue;}if(m_or_ke){//必選已經出來了if(x-maxn[i]>mr)must_n.push_back(i);//直接加必選if(x-maxn[i]<=r)no_n.push_back(i);//不可選continue;}if(x-maxn[i]>mr){if(!m_or_ke)must_n.clear();m_or_ke = true;must_n.push_back(i);}else if(x-maxn[i]>r){must_n.push_back(i);}else{no_n.push_back(i);//不可選}}//預處理bool mn_[n+1];for(int i=1;i<=n;i++)mn_[i]=false;for(auto xx:must_n)mn_[xx]=true;for(auto xx:no_n)mn_[xx]=false;//must_n -> must_chose//for(int i=1;i<=nx;i++){//可優化//    if(mn_[v[i].first]&&mn_[v[i].second])must_chose.push_back(i);//}for(int i=1;i<=n;i++){//優化后if(!mn_[i])continue;for(int j=i+1;j<=n;j++){if(mn_[j]){must_chose.push_back(mv[{i,j}]);}}}int mi = must_chose.size();for(int i=0;i<mi;i++){//checkif(ans[v[must_chose[i]].first][v[must_chose[i]].second])continue;//chosechose[x] = must_chose[i];ans[v[must_chose[i]].first][v[must_chose[i]].second] = x;ans[v[must_chose[i]].second][v[must_chose[i]].first] = x;int vf_maxn = maxn[v[must_chose[i]].first];//備份int vs_maxn = maxn[v[must_chose[i]].second];maxn[v[must_chose[i]].first] = maxn[v[must_chose[i]].second] = x;f(x+1);//cut choseans[v[must_chose[i]].first][v[must_chose[i]].second] = 0;maxn[v[must_chose[i]].first] = vf_maxn;maxn[v[must_chose[i]].second] = vs_maxn;}
}
inline void print_ans(){for(int i=1;i<=n;i++){vector<int>v1;for(int j=1;j<=n;j++){cout << ans[i][j] << ' ';v1.push_back(ans[i][j]);}sort(v1.begin(),v1.end());cout << ',';for(int j=2;j<n;j++){cout << v1[j]-v1[j-1]-1 << ' ';}cout << '\n';}return ;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout << ans[i][j] << ' ';cout << '\n';}
}

代入n=9 / n=8答案可出