单循环赛，每个队参加前后两场比赛之间的距离最大，这就是这个问题的要求。
这个问题，使用简单回溯，剪剪枝好像可以，但是要当n很大的时候就很为难，速度什么的成了问题。所以这里，我使用了近似算法。
观察问题，发现这是一个对称矩阵的问题，那么我有几条启发式规则：
（1）插入矩阵的元素，不应该和前 m 的元素同行很列。
这个，很简单可以理解，这是为了使最小间距得意保证。
（2）插入的位置，应尽可能在行或者列上占据更多的空格。
这个，有一点难理解，主要是先插入的元素理应占有利位置，这样越往后，差距变大的可能性就提高了。
否则当后面插入时，差距就会变小
（3）插入位置理应和个行列产生最大的行间距。
这个也好理解，主要是为了保证最小间距最大。
（4）插入位置理应靠近上三角的中心。
这个还是为了保证插入时能很有效的满意。
之后，我们便是不断地尝试（1）里面提到的m的值。这里，我们先来估计一下m的上界吧。假设最小间距为m，那么（i，j） 先比赛，比赛之后就是（i，k）比赛，这样必须除了i,j,k之外还至少有2m个球队，所以 n >= 2m + 3;也就是 m <= [(n-3)/2];
这样，我们便开始从m的上界开始，向下检索。
#include "stdafx.h" #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; class class_last_one { private: const int MAX_USE; vector<vector<int>> matrix; int n; private: double get_min_weight(int pos_i,int pos_j,int val) { double re = 0.0; for(int cnt_i=0;cnt_i<n;cnt_i++) { for(int cnt_j=0;cnt_j<n;cnt_j++) { if (matrix[cnt_i][cnt_j] != MAX_USE && matrix[cnt_i][cnt_j] != 0) { re += (abs(cnt_i - pos_i) + abs(cnt_j - pos_j))*(val - matrix[cnt_i][cnt_j]); } } } return re; } int get_min_dis_for_each_form_zero(int pos_i,int pos_j,int val) { int re = 0; for(int cnt=0;cnt<n;cnt++) { if (matrix[pos_i][cnt] <= n && matrix[pos_i][cnt] !=0 ) re += val - matrix[pos_i][cnt]; } for(int cnt=0;cnt<n;cnt++) { if (matrix[cnt][pos_j] <= n && matrix[cnt][pos_j] !=0 ) re += val - matrix[cnt][pos_j] ; } return re; } int get_min_dis_for_each(int pos_i,int pos_j,int val) { int re = 0; for(int cnt=pos_i;cnt<pos_j;cnt++) { if (matrix[pos_j][cnt] <= n && matrix[pos_j][cnt] !=0 ) re += val - matrix[pos_j][cnt]; } for(int cnt=pos_j;cnt<n;cnt++) { if (matrix[pos_j][cnt] <= n && matrix[pos_j][cnt] !=0 ) re += val - matrix[pos_j][cnt] ; } return re; } int get_min_dis(int pos_i,int pos_j,int val) { if (pos_i<mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js"></mce:script><mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js"></mce:script> == pos_j) return MAX_USE; int re = MAX_USE; for(int cnt=0;cnt<n;cnt++) { if (matrix[pos_i][cnt] <= n && matrix[pos_i][cnt] !=0 && val - matrix[pos_i][cnt] < re) re = val - matrix[pos_i][cnt]; } for(int cnt=0;cnt<n;cnt++) { if (matrix[cnt][pos_j] <= n && matrix[cnt][pos_j] !=0 && val - matrix[cnt][pos_j] < re) re = val - matrix[cnt][pos_j]; } return re; } int get_space(int pos_i,int pos_j) { if (pos_i == pos_j) return 0; int re = 0; for(int cnt=0;cnt<n;cnt++) { if (matrix[pos_i][cnt] == 0) re++; } for(int cnt=0;cnt<n;cnt++) { if (matrix[cnt][pos_j] == 0) re++; } return re; } int get_dis_from_center(int pos_i,int pos_j) { return abs(pos_i - n/3) + abs(pos_j - 2*n/3); } bool set_matrix(int n_pre) { init_matrix(); vector<int> pos_pre; vector<bool> b_larger; b_larger.push_back(true); b_larger.push_back(true); b_larger.push_back(false); vector<int> vct_cur(3); vector<int> vct_use(3); for(int cnt=1;cnt<=n*(n-1)/2;cnt++) { vct_use[0] = (-1); //space vct_use[1] = (-1); //dis vct_use[2] = (MAX_USE);//center int pos_do_i = -1; int pos_do_j = -1; for(int pos_i=0;pos_i<n;pos_i++) { for(int pos_j=pos_i+1;pos_j<n;pos_j++) { if (matrix[pos_i][pos_j] != 0) continue; bool b_continue = false; for(int cnt_k=2*n_pre;cnt_k >0 && pos_pre.size() > n_pre*2 - cnt_k;cnt_k--) { if (pos_i == pos_pre[pos_pre.size() -1 - 2*n_pre + cnt_k] || pos_j == pos_pre[pos_pre.size() -1 - 2*n_pre + cnt_k]) { b_continue = true; break; } } if (b_continue == true) continue; vct_cur[0] = get_space(pos_i,pos_j); vct_cur[1] = get_min_dis_for_each_form_zero(pos_i,pos_j,cnt); vct_cur[2] = get_dis_from_center(pos_i,pos_j); if (check_record_for_diff_weight(vct_cur,vct_use,b_larger)) { vct_use = vct_cur; pos_do_i = pos_i; pos_do_j = pos_j; } } } if (pos_do_i == -1 || pos_do_j == -1) return false; matrix[pos_do_i][pos_do_j] = cnt; matrix[pos_do_j][pos_do_i] = cnt; pos_pre.push_back(pos_do_i); pos_pre.push_back(pos_do_j); } return true; } bool check_record_for_diff_weight(const vector<int>& cur,const vector<int>& use,const vector<bool>& b_larger) { for(int cnt=0;cnt<cur.size();cnt++) { if (cur[cnt] == use[cnt]) continue; if (b_larger[cnt] == true) { if (cur[cnt]>use[cnt]) return true; else return false; } else { if (cur[cnt] < use[cnt]) return true; else return false; } } return true; } double get_weight(int n_space,int n_dis) { if (n_dis != MAX_USE) return n_space*n_space*n_space*n_dis*n_dis / (n*n); else return n_space*n_space*n_space; } int get_min_result() { int n_min = n+1; for(int cnt=0;cnt<n;cnt++) { sort(matrix[cnt].begin(),matrix[cnt].end()); for(int cnt_cur=0;cnt_cur<n-1;cnt_cur++) { if (matrix[cnt][cnt_cur+1] - matrix[cnt][cnt_cur] < n_min) n_min = matrix[cnt][cnt_cur+1] - matrix[cnt][cnt_cur]; } } return n_min; } void init_matrix() { matrix.clear(); matrix.resize(n); for(int cnt_i=0;cnt_i<n;cnt_i++) { matrix[cnt_i].resize(n,0); matrix[cnt_i][cnt_i] = MAX_USE; } } public: void display_matrix() { for(int cnt_i=0;cnt_i<n;cnt_i++) { for(int cnt_j=0;cnt_j<n;cnt_j++) { cout<<matrix[cnt_i][cnt_j]<<"/t"; } cout<<endl; } } int try_matrix_muti_times() { vector<vector<int>> matrix_bake_up; int error = 0; int n_times = 1; init_matrix(); matrix_bake_up = matrix; while(error != 3) { if (set_matrix(n_times) == false) error++; else matrix_bake_up = matrix; if (error == 0) n_times = get_min_result(); else n_times ++; } matrix = matrix_bake_up; return get_min_result(); } int try_matrix() { vector<vector<int>> matrix_bake_up; int n_times = 1; int n_re = 0; init_matrix(); matrix_bake_up = matrix; while(set_matrix(n_times)) { n_re = get_min_result(); n_times = n_re; matrix_bake_up = matrix; } matrix = matrix_bake_up; return get_min_result(); } class_last_one(int a_n):MAX_USE(a_n*a_n+100) { n = a_n; } }; int _tmain(int argc, _TCHAR* argv[]) { for(int cnt=5;cnt<100;cnt++) { class_last_one lo(cnt); cout<<cnt<<":"<<lo.try_matrix()<<endl; } return 0; }
结果如下：（5 到 49，result是结果，der_result_for_ideal_bound 是与理想上界的差，cpu_clock是消耗的cpu时钟数）
5: result = 2 , der_result_for_ideal_bound = 0 , cpu_clock = 1
6: result = 2 , der_result_for_ideal_bound = 0 , cpu_clock = 10
7: result = 2 , der_result_for_ideal_bound = 1 , cpu_clock = 10
8: result = 2 , der_result_for_ideal_bound = 1 , cpu_clock = 10
9: result = 3 , der_result_for_ideal_bound = 1 , cpu_clock = 10
10: result = 3 , der_result_for_ideal_bound = 1 , cpu_clock = 20
11: result = 4 , der_result_for_ideal_bound = 1 , cpu_clock = 20
12: result = 4 , der_result_for_ideal_bound = 1 , cpu_clock = 20
13: result = 4 , der_result_for_ideal_bound = 2 , cpu_clock = 50
14: result = 5 , der_result_for_ideal_bound = 1 , cpu_clock = 40
15: result = 5 , der_result_for_ideal_bound = 2 , cpu_clock = 80
16: result = 5 , der_result_for_ideal_bound = 2 , cpu_clock = 120
17: result = 6 , der_result_for_ideal_bound = 2 , cpu_clock = 130
18: result = 6 , der_result_for_ideal_bound = 2 , cpu_clock = 210
19: result = 6 , der_result_for_ideal_bound = 3 , cpu_clock = 320
20: result = 7 , der_result_for_ideal_bound = 2 , cpu_clock = 260
21: result = 7 , der_result_for_ideal_bound = 3 , cpu_clock = 420
22: result = 7 , der_result_for_ideal_bound = 3 , cpu_clock = 580
23: result = 8 , der_result_for_ideal_bound = 3 , cpu_clock = 630
24: result = 8 , der_result_for_ideal_bound = 3 , cpu_clock = 660
25: result = 8 , der_result_for_ideal_bound = 4 , cpu_clock = 1270
26: result = 9 , der_result_for_ideal_bound = 3 , cpu_clock = 1070
27: result = 10 , der_result_for_ideal_bound = 3 , cpu_clock = 1040
28: result = 10 , der_result_for_ideal_bound = 3 , cpu_clock = 1350
29: result = 10 , der_result_for_ideal_bound = 4 , cpu_clock = 2120
30: result = 11 , der_result_for_ideal_bound = 3 , cpu_clock = 6260
31: result = 11 , der_result_for_ideal_bound = 4 , cpu_clock = 2700
32: result = 11 , der_result_for_ideal_bound = 4 , cpu_clock = 2950
33: result = 11 , der_result_for_ideal_bound = 5 , cpu_clock = 8080
34: result = 12 , der_result_for_ideal_bound = 4 , cpu_clock = 4310
35: result = 13 , der_result_for_ideal_bound = 4 , cpu_clock = 4110
36: result = 13 , der_result_for_ideal_bound = 4 , cpu_clock = 7970
37: result = 14 , der_result_for_ideal_bound = 4 , cpu_clock = 5230
38: result = 13 , der_result_for_ideal_bound = 5 , cpu_clock = 9520
39: result = 14 , der_result_for_ideal_bound = 5 , cpu_clock = 8910
40: result = 14 , der_result_for_ideal_bound = 5 , cpu_clock = 14410
41: result = 15 , der_result_for_ideal_bound = 5 , cpu_clock = 20310
42: result = 14 , der_result_for_ideal_bound = 6 , cpu_clock = 25880
43: result = 15 , der_result_for_ideal_bound = 6 , cpu_clock = 27760
44: result = 16 , der_result_for_ideal_bound = 5 , cpu_clock = 27790
45: result = 14 , der_result_for_ideal_bound = 8 , cpu_clock = 65320
46: result = 16 , der_result_for_ideal_bound = 6 , cpu_clock = 45770
47: result = 16 , der_result_for_ideal_bound = 7 , cpu_clock = 49920
48: result = 17 , der_result_for_ideal_bound = 6 , cpu_clock = 56730
49: result = 17 , der_result_for_ideal_bound = 7 , cpu_clock = 60300
total_clock:1004671
