世界杯(worldcup)题解

题目

世界杯(worldcup)

题目描述

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位。

样例

输入

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

输出

85.64
78.00

提示

对于30%数据，K, D, M, F≤1000，Q≤10；
对于100%数据，1≤K, D, M, F≤10^5，0≤k_i, d_i, m_i, f_i≤10^8，1≤Q≤K，0≤A_i, B_i, C_i≤10，A_i+B_i+C_i=10，∑A_i≤D，∑B_i≤M，∑C_i≤F。

时间限制: 1.000 Sec
内存限制: 128 MB
来源：Luo’s OJ && 洛谷

题解

这题用优先队列！！！

优先队列是队列，先要包含头文件#include , 它和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

接下来看code吧~

#include<bits/stdc++.h>
using namespace std;
int n1,n2,n3,n4,T;
priority_queue <int,vector<int>,less<int> >q1,q2,q3,q4; //定义优先队列 
//降序队列
int main(){
	scanf("%d%d%d%d",&n1,&n2,&n3,&n4); //输入 
	for (int i = 1; i <= n1; i++) {
		int a;
		scanf("%d",&a);
		q1.push(a); //入队 
	} 
	for (int i = 1; i <= n2; i++) { //这些都是第一个循环复制下来，微调的 
		int a;
		scanf("%d",&a);
		q2.push(a);
	} 
	for (int i = 1; i <= n3; i++) {
		int a;
		scanf("%d",&a);
		q3.push(a);
	} 
	for (int i = 1; i <= n4; i++) {
		int a;
		scanf("%d",&a);
		q4.push(a);
	} 
	scanf("%d",&T);
	while (T--){ //同样，按题意模拟即可 
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		double sum = 0.0;
		sum += q1.top();
		q1.pop();
		for (int i = 1; i <= a; i++){
			sum += q2.top(); //读取元素 
			q2.pop(); //弹出 
		}
		for (int i = 1; i <= b; i++){ //复制黏贴 
			sum += q3.top();
			q3.pop();
		}
		for (int i = 1; i <= c; i++){
			sum += q4.top();
			q4.pop();
		}
		printf("%.2lf\n",(sum/11)); //最后输出即可 
	}
	return 0;
}

测评结果 正确
内存(KB) 4444KB
耗时(MS) 349ms
语言 C++
代码长度 909 bytes