P3887 [GDOI2014]世界杯

# [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 476 60 8778 84 84 84 81 82 72 51 77 5785 84 62 87 88 64 81 90 80 66 88 8565 83 63 7924 5 14 4 2```

### 样例输出 #1

```85.6478.00```

代码及思路展示

#include#include//queue的头文件#include//sort需要用到的头文件using namespace std;int main(){ long long K,D,M,F; cin>>K>>D>>M>>F;//分别表示守门员、后卫、中场和前锋供挑选的球员人数 long long n[100005]={0};//n数组用来暂存数据，即分数 queuek,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;}