马拉松接力赛
题目描述
某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。
刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、…、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。
根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑2km速度快，连续跑2km又要比连续跑3km速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。
输入输出格式
输入格式：
5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、…、10km所用的时间。
输出格式：
两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。
输入样例
333 700 1200 1710 2240 2770 3345 3956 4778 5899 300 610 960 1370 1800 2712 3734 4834 5998 7682 298 612 990 1540 2109 2896 3790 4747 5996 7654 289 577 890 1381 1976 2734 3876 5378 6890 9876 312 633 995 1407 1845 2634 3636 4812 5999 8123
输出样例
9905 6 5 5 4 5
乍一看，发现用全排列可以写，毕竟只有10 ^ 5 种情况，但若是10 个人的话就10 ^ 10 种，超时。可见用全排列一定不是最优的。
再想一想，也可以用dfs，从第一个人跑1千米开始，不过弊端也是数据大了会超时，不可取。
铺垫了不少，该引出正解了：思考一下，因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快……那么连续跑的路程越长，速度越慢。所以我们可以先预处理一下，计算出每一位选手跑每一公里所用的时间。
这样的话对于接下来的1公里，只要取每一位选手要跑的下一公里中用时最短的那一个，那么这个最短时间就代表了该1公里的最短时间，每一公里的最短时间之和就是最终的最短时间。局部最优推出全局最优。
顺便一提，1、计算最终最短时间只用跑过的公里的最短时间加上该1公里的最短时间
2、可以开一个b[6] 数组记录每一个运动员跑的公里数，若第 i 位运动员该公里所用时间最少，那么 b[i]++。
3、对了，b 数组初始状态应全是1，因为每个运动员最少跑1公里。同时 b[i] <= 10
哒哒
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<stack> 7 #include<cmath> 8 #include<string> 9 #include<cstdlib> 10 #include<ctime> //无视头文件 11 using namespace std; 12 typedef long long ll; 13 int a[6][11], b[6][11], tot[6] = {0}; 14 ll ans = 0; 15 int main() 16 { 17 freopen("marath.in", "r", stdin); 18 freopen("marath.out", "w", stdout); 19 for(int i = 1; i <= 5; ++i) 20 for(int j = 1; j <= 10; ++j) 21 { 22 scanf("%d", &a[i][j]); 23 b[i][j] = a[i][j] - a[i][j - 1]; //b数组用来存放每一运动员每一公里所用时间 24 } 25 for(int i = 1; i <= 5; ++i) {ans+= b[i][1]; tot[i] = 2;}//每一位运动员都该跑第2公里 26 int n = 20; //还剩20公里 27 while(n--) 28 { 29 int min = 999999, vis; //别忘了 min 每一次都要初始化为一个很大的值 30 //min 存该公里最少时间， vis 存跑最少时间的运动员序号 31 for(int i = 1; i <= 5; ++i) 32 if(b[i][tot[i]] < min && tot[i] <= 10) 33 { 34 min = b[i][tot[i]]; vis = i; 35 } 36 ans += b[vis][tot[vis]]; tot[vis]++; 37 } 38 printf("%lld ", ans); 39 for(int i = 1; i <= 5; ++i) printf("%d ", tot[i] - 1); 40 //tot[i] 代表第 i 位运动员该跑第 tot[i] 公里，所以实际上跑了tot[i] - 1 公里 41 printf(" "); 42 return 0; 43 }
完美收尾。