# [GDOI2014]世界杯
## 题目描述
3014 年世界杯足球赛就要开始了!作为卫冕冠军中国足球队的教练,手下每位球员都是猛将,如何摆出最强的 11 人阵容也是一件幸福的烦恼事啊。
众所周知,足球阵容里的11个球员都会被分配到场上某一个特别的位置,而这些位置主要分为守门员、后卫、中场和前锋四种,其中守门员有且只有一个,后卫、中场和前锋的人数取决于你安排的足球阵型。形容足球阵型的方法由后卫开始计算至前锋,但不把守门员计算在内。例如,3-5-2 阵型是指有三个后卫、五个中场及两名前锋。由于竞争激烈,每位球员只会培养其中一种位置所需要的技能,所以他们每个人都只能胜任四个位置中的其中一种。
作为一个对球员能力了如指掌的教练,你给每个球员的综合水平进行量化。为了将阵型安排得更好,你的教练团队决定使用以下策略安排球员:首先按照顺序提出 Q个阵型,分别代表第一阵型、第二阵型、……、第 Q阵型。然后对于每个阵型,从仍未选择的球员中选择最好的对应数量的守门员、后卫、中场和前锋。比如说,对于第一阵型,在所有球员中选择;对于第二阵型,在除了第一阵型外的所有球员中选择;对于第三阵型,在除了第一阵型和第二阵型外的所有球员中选择;以此类推。
现在 Q个阵型都已经确定,而你需要知道的,是每个阵型的平均综合水平分别是多少。
## 输入格式
第一行有四个整数 K, D, M, F,分别表示守门员、后卫、中场和前锋供挑选的球员人数。
第二行有 K个整数 k_i,分别表示每个守门员的综合水平值。
第三行有 D个整数 d_i,分别表示每个后卫的综合水平值。
第四行有 M 个整数 m_i,分别表示每个中场的综合水平值。
第五行有 F个整数 f_i,分别表示每个前锋的综合水平值。
第六行有一个整数 Q,表示教练团队提出的阵型个数。
以下Q行,第 i 行三个整数A_i, B_i, C_i$,由空格间隔,表示第 i 阵型是 A_i - B_i - C_i 阵型。
## 输出格式
输出 Q行。对于第 i 种阵型,输出一个实数,表示该阵型平均综合水平的最大值,并四舍五入到小数点后2 位。
## 样例 #1
### 样例输入 #1
```
3 10 12 4
76 60 87
78 84 84 84 81 82 72 51 77 57
85 84 62 87 88 64 81 90 80 66 88 85
65 83 63 79
2
4 5 1
4 4 2
```
### 样例输出 #1
```
85.64
78.00
```
代码及思路展示
#include<iostream>
#include<queue>//queue的头文件
#include<algorithm>//sort需要用到的头文件
using namespace std;
int main()
{
long long K,D,M,F;
cin>>K>>D>>M>>F;//分别表示守门员、后卫、中场和前锋供挑选的球员人数
long long n[100005]={0};//n数组用来暂存数据,即分数
queue<long long>k,d,m,f;//构造4个队列,存储如上数据的分数
for(int i=1;i<=K;i++)
{//输入每个守门员的分数
cin>>n[i];
}
sort(n+1,n+1+K);
//首先进行排序,从小到大
for(int i=K;i>=1;i--)
{
k.push(n[i]);//但是此处是从最大到最小的顺序入栈,方便后面的操作
}
for(int i=1;i<=D;i++)
{//同上操作,后卫分数
cin>>n[i];
}
sort(n+1,n+1+D);
for(int i=D;i>=1;i--)
{
d.push(n[i]);
}
for(int i=1;i<=M;i++)
{//同上操作,中锋分数
cin>>n[i];
}
sort(n+1,n+1+M);
for(int i=M;i>=1;i--)
{
m.push(n[i]);
}
for(int i=1;i<=F;i++)
{//同上操作,前锋分数
cin>>n[i];
}
sort(n+1,n+1+F);
for(int i=F;i>=1;i--)
{
f.push(n[i]);
}
int Q;
cin>>Q;//输入想要几支队伍
int a,b,c;//队伍的类型
double ans;//该队伍的总分
for(int i=1;i<=Q;i++)
{
ans=0;
cin>>a>>b>>c;
//由于之前入栈的每个种类队员的分数都按照从大到小的顺序排好了
//此处的操作是,比如需要a个后卫,则从栈中取出前a个,然后出栈
//保证下一次操作时,是前几次选拔完后的队员中,剩余的最好的队员被优先选中
for(int j=1;j<=a;j++)ans+=d.front(),d.pop();
for(int j=1;j<=b;j++)ans+=m.front(),m.pop();
for(int j=1;j<=c;j++)ans+=f.front(),f.pop();
ans+=k.front();//别忘了加上守门员
k.pop();
printf("%.2f\n",double(ans/11));//最后按照要求输出
}
return 0;
}