题解 P3887 【[GDOI2014]世界杯】

· · 题解

我也不知道为什么没人打暴力，10的五次方O(10n)轻松能过，甚至不需要读入优化。

思路：守门员单算，比较简单，剩下三种类型的拿中场说。

假设你有16个中场球员，他们是：（表格纯手打）（剩下几名球员power从60到72不等）

 -------------- --------------  
|   name       | power        |
| -----------: | -----------: |
|    666       | 22           |
|    god       | 88           |
|    messi     | 99           |
|              |              |
 -------------- --------------

4套阵容，分别要求3,4,3,6个中场球员

那第一套肯定是god，messi和72的那位了。

你会发现一个规律：

排完序后，power 分别是 99,88,72,71,70,69,68,67……60,22

每次抽剩下人里的前i个就行了。

看代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005],d[100005];
int k,g,f,m,q;
double tbh;
bool cmp(int a,int b){//从大至少排序
    return a>b;
}
int main(){
    cin>>k>>g>>f>>m;
    for(int i=1;i<=k;i++)
       cin>>a[i];
    for(int i=1;i<=g;i++)
       cin>>b[i];
    for(int i=1;i<=f;i++)
       cin>>c[i];
    for(int i=1;i<=m;i++) //往死里输入
       cin>>d[i];
    sort(a+1,a+k+1,cmp);
    sort(b+1,b+g+1,cmp);
    sort(c+1,c+f+1,cmp);
    sort(d+1,d+m+1,cmp);//往死里排序
    cin>>q;
    int l,z,y;
    int x=1,r=1,w=1,h=1;
    int sss;
    while(q--){
        cin>>l>>z>>y;
        tbh=0;
        tbh+=a[x];//守门员
        x++;//序号++
        for(int i=r;i<r+l;i++)
           tbh+=b[i];//后卫
        r+=l;
        for(int i=w;i<w+z;i++)
           tbh+=c[i];//中场
        w+=z;
        for(int i=h;i<h+y;i++)
           tbh+=d[i];//前锋
        h+=y;
        printf("%.2f\n",tbh/11);//一共十一人
    }
    return 0;
}