P3887 [GDOI2014]世界杯

    • 824通过
    • 1.7K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 优先队列 排序 队列 各省省选 2014 广东 高性能
  • 难度 普及-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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: 复制
    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
    

    说明

    对于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。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。