混战世界

cstdio1 2019-08-17 原文

题目分析：假设一个人的物理攻击为A，法术攻击为B，如果进入阵营1贡献是A，如果进入阵营2贡献是B，进入阵营3贡献为（A+B）/2；

现在要考虑进入哪个阵营贡献最大就去哪个阵容，如果所有的人都是这么选择就可以得到全局的最大和。

比较常用的就是做差：

对阵营1的贡献 – 对阵营2的贡献 = 　　A – B

对阵营1的贡献 – 对阵营3的贡献 = 　（A – B）/ 2

对阵营3的贡献 – 对阵营2的贡献 =　　（A – B）/ 2

A-B>0得到对阵营1的贡献 > 对阵营2的贡献

　　　　　　对阵营1的贡献 > 对阵营3的贡献

　　　　　　对阵营3的贡献 > 对阵营2的贡献

　　　　　　从而得到：对阵营1的贡献 > 对阵营3的贡献 > 对阵营2的贡献

　　　　　　换句话说就是A-B越大此时选择的顺序就应该是：阵营1 > 阵营3> 阵营2

所以就需要对数组a[i]-b[i]进行排序，但是需要记住排序后最大到最小的序号值而不是a[i] – b[i] .

c++代码如下：

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+5;
int a[N],b[N],c[N];//物理攻击，魔法攻击 

bool cmp(int l,int r){//关键的比较函数 
    return a[l]-b[l]>a[r]-b[r];
}                   
int main()
{
    int n;//人数 
    double ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>a[i];    
    }
    for(int i=1;i<=n;i++){
    cin>>b[i];    
    }
    for(int i=1;i<=n;i++){//初始化c数组 
    c[i]=i;    
    }
    sort(c+1,c+1+n,cmp);
    int k=n/3;
    for(int i=1;i<=n;i++){
    if(i<=k){
    ans+=a[c[i]];    
    }
    else if(i<=2*k){
    ans+=(a[c[i]]+b[c[i]])/2.0;    
    }
    else{
    ans+=b[c[i]];    
    }    
    }printf("%.2lf",ans);

    return 0;
}