1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116---
layout: post
title: "每周ACM之一：最强Dota阵容"
date: 2013-12-24 12:00:00
category: acm
summary: "每周ACM，第一期，最强Dota阵容。"
---
DOTA（Defense of the Ancients）是一款及时战略游戏，现在特别火热，相信大家很多人都玩过。
DOTA将10个游戏玩家分为两组，分别为天灾和近卫，推倒对方主基地的一方获得胜利。
每个玩家可以选择一个英雄作为游戏中的角色。
每个角色有三个属性：力量，敏捷，智力。选人的策略对比赛的胜负非常关键，现在需要你找出最平衡的一套阵容（5个英雄）。
这里对平衡性F做个很简单的定义：设E1是一套阵容力量的平均数，E2是敏捷的平均数，E3是智力的平均数，F是E1，E2，E3的方差， F越小越平衡。
### Input
第一行一个正整数 C 表示一共有多少组数据
对于每一组数据：
第一行一个正整数N，表示这组英雄的个数 `（5<=N<=20）`
接下来的N行每行有4个整数 B，L，M，Z 表示该英雄编号为B，力量为L，敏捷为M，智力为Z。
`(1<=B<=N 0<L, M, Z<1000)`
### Output
对于每组数据，输出一行为最平衡的一套阵容（5个英雄的编号），英雄的编号需要从小到大排列，如果存在多组解输出英雄编号字典序最小的。
### Sample Input
{% highlight text %}
1
6
3 1 1 1
2 1 1 1
1 7 8 9
4 1 1 1
5 1 1 1
6 1 1 1
{% endhighlight %}
### Sample Output
{% highlight text %}
2 3 4 5 6
{% endhighlight %}
**【答案如下】**
只是一道非常简单的题，直接枚举即可。
{% highlight c++ %}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
int id;
double li, zhi, min;
} hero[20];
int cmp(node x, node y) {
return x.id < y.id;
}
int main() {
int t, i, x1, x2, x3, x4, x5;
double li, min, zhi, minn, ping, s;
int f1, f2, f3, f4, f5;
scanf("%d", &t);
while (t--) {
minn = 10000000;
int n;
scanf("%d", &n);
for(i = 0; i < n; i ++) {
scanf("%d%lf%lf%lf", &hero[i].id, &hero[i].li, &hero[i].min, &hero[i].zhi);
}
sort(hero, hero + n, cmp);
for(x1 = 0; x1 < n - 4; x1 ++) {
for(x2 = x1 + 1; x2 < n - 3; x2 ++) {
for(x3 = x2 + 1; x3 < n-2; x3 ++) {
for(x4 = x3 + 1; x4 < n-1; x4 ++) {
for(x5 = x4 + 1; x5 < n; x5 ++) {
li = (hero[x1].li + hero[x2].li + hero[x3].li + hero[x4].li + hero[x5].li) / 5;
min = (hero[x1].min + hero[x2].min + hero[x3].min + hero[x4].min + hero[x5].min) / 5;
zhi = (hero[x1].zhi + hero[x2].zhi + hero[x3].zhi + hero[x4].zhi + hero[x5].zhi) / 5;
ping = (li + min + zhi) / 3;
s = ((li - ping) * (li - ping) + (min - ping) * (min - ping) + (zhi - ping) * (zhi - ping)) / 3;
if (s < minn) {
f1 = hero[x1].id;
f2 = hero[x2].id;
f3 = hero[x3].id;
f4 = hero[x4].id;
f5 = hero[x5].id;
minn = s;
}
}
}
}
}
}
printf("%d %d %d %d %d\n", f1, f2, f3, f4, f5);
}
return 0;
}
{% endhighlight %}