相信大家都看了出题人的题解了。首先,我们在这里要理解到两人都希望把得分尽量比对方大这句话的含义。假如我们是其中一方,我们要尽量与对方拉开差距,那么我们如何实现呢?就相当于考试,我们想要比他人排名更高的话,我们就要考得更高,亦或是对手要考的更低。在这个场景中,假如我们是牛牛,那么我就要尽量拿走当前物品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