牛客寒假算法基础集训营2题解（F题）

相信大家都看了出题人的题解了。首先，我们在这里要理解到两人都希望把得分尽量比对方大这句话的含义。假如我们是其中一方，我们要尽量与对方拉开差距，那么我们如何实现呢？就相当于考试，我们想要比他人排名更高的话，我们就要考得更高，亦或是对手要考的更低。在这个场景中，假如我们是牛牛，那么我就要尽量拿走当前物品A属性最高的，最好就同时把物品的B属性最高的拿走，当然，这种情况过于特殊化了，那么就普通的吧。其实，拿分最高的物品可以从A，B两者考虑，我可以只拿当前物品A的属性最高的，也可以只拿物品B的属性当前最高的。拿物品A属性高的大家很好理解，但是对于物品的B属性，拿走B属性更高的其实也是在压低对方的得分。也就是自己与对方的差距拉得更大了，这就是最优策略。所以，我们要同时考虑物品的A，B属性，也就得到了要拿当前物品A，B属性总和最高的。（我不知道这样解释你们可不可以理解，但希望可以静下心来仔细想想是不是这样的道理）出题人给出了具体的公式，我这也算是在强行解释了。下面是出题人的解释：

到了这里，我们的目的就很明确了。我们把每个物品的a，b属性的和计算出来，在进行排序，然后按从大到小的顺序依次拿，但这里就有一个问题了，排过序的同学都知道，排序之后，数组的下标也会跟着改变，因为在这里下标是与地址相关联的，排序会改变原地址，原下标也随之改变。那么，我们有什么办法让下标与地址不相关联吗？或是排序时可以让下标与其一起改变呢？这里，我们介绍一个方法，就是对结构体进行排序。我们把相加的和用一个数表示，并且用另一个数记录其下标。对结构体排序只会按其某一个成员进行排序，不会改变其他成员的值。这就是我们想要的。

struct node{
    ll c;
    ll ans;
}res[N];

这里，我们把每个物体的a，b分数相加之和用c记录，把下标用ans进行记录。

bool cmp(node n1,node n2){
    return n1.c>n2.c;
}

这个函数是我们等下要用的sort函数（包含在algorithm里面的库函数）的时候要用到的参数，因为sort函数默认是从小到大排序，我们要改为从大到小排序就要把这个当成参数加入其中（不懂得建议先去自行百度sort函数），其实要默认也可以，只是后面处理更加复杂一点。这里我们方便理解就用这个当作参数吧。注意，我们在这个函数里规定以结构体里的c的大小进行排序（从大到小）。如果把小于号反过来就是从小到大，当然，没必要，因为这是默认的。

sort(res+1,res+1+n,cmp);

这个就是排序函数，但是我们这里是对结构体的某一个成员进行排序。在cmp函数里已经规定好了用c的大小。
接下来，就是总的代码

//万能头文件 
#include<bits/stdc++.h>
using namespace std;
const int N=200020;
typedef long long ll;
struct node{
    ll c;
    ll ans;
}res[N];
bool cmp(node n1,node n2){
    //以结构体c的大小按从大到小排序 
    return n1.c>n2.c;
}
ll a[N],b[N];
int main(){
    int n;
    cin>>n;
//因为物品计数是从1开始的，所以建议从1开始枚举，之后好记录下标，也就是该物品是第几件物品
    for(int i=1;i<=n;i++){
        cin>>a[i];
        res[i].c=a[i];   //把当前物品A属性赋给当前结构体的成员c 
        res[i].ans=i;  //在这里同时记录好下标存入结构体的ans成员，所以输入b的数据时就不必再这步了 
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        res[i].c+=b[i];   //当前结构体的c加上B属性 
    }
    //到了这里我们已经收集好了每件物品的A，B属性之和，也记下了相应的下标存入res数组的元素里（也就是结构体） 
    sort(res+1,res+1+n,cmp);
    //在排好序后，我们的每个结构体中的c是按大小排的，而且它最初的下标也还记着 
    for(int i=1;i<=n;i++){
        //牛牛先拿，所以就是拿到奇数输出当前结构体的ans成员，也就是原下标 
        if(i%2==1)  cout<<res[i].ans<<" ";
    }
    cout<<endl;
    for(int i=2;i<=n;i++){
        //牛可乐拿到偶数，遇到偶数就输出当前结构体中的ans成员
        if(i%2==0)  cout<<res[i].ans<<" ";
    }
    return 0;
}

总体思路就是这样，有疑问下方留言。
附：
牛客寒假算法基础训练营2题解C题：https://blog.nowcoder.net/n/9d821b9b4f2445749680a2777d4746cd