归并排序看不明白点[这里](https://visualgo.net/zh/sorting?slide=1)
我写了一个归并排序,开O2能得80分
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2*1e5+10;
struct f{
int id;
ll fen;
int shi;
}a[N],b[N];//b数组用于归并排序
bool cmp(f a,f b)
{
if(a.fen==b.fen)return a.id<b.id;
return a.fen>b.fen;
}
void mergesort(int l,int r)
{
if(l==r)
return ;//分到叶子结点,返回进行排序
int mid=(l+r)/2;//取中点
mergesort(l,mid);
mergesort(mid+1,r);//分成两半排序
int i=l,j=mid+1,k=l;//i指向l~mid的区间,j指向mid+1~r的区间,k进行扔到b数组里边
while(i<=mid&&j<=r)//给两边排序,直到有一边为空
{
if(cmp(a[i],a[j]))//比较大小,a[i]>a[j]
b[k++]=a[i++];//取i位置为更前面的,并将i向前移动一位
else
b[k++]=a[j++];//取j位置为更前面的,并将j向前移动一位
}
//进行剩余处理
while(i<=mid)
b[k++]=a[i++];//如果左半边取空了,那该行不会执行
while(j<=r)
b[k++]=a[j++];//如果右半边取空了,那该行不会执行
for(i=l;i<=r;i++)
a[i]=b[i];//用排序后的l~r区间更新原来的l~r区间
//该段归并排序结束
}
int main(){
int n,r,q;
cin>>n>>r>>q;
for(int i=1;i<=n*2;i++)
{
cin>>a[i].fen;
a[i].id=i;
}
for(int i=1;i<=n*2;i++)
{
cin>>a[i].shi;
}
while(r--)
{
mergesort(1,n*2);
for(int i=1;i<=n*2;i+=2)
{
if(a[i].shi<a[i+1].shi)
a[i+1].fen++;
else a[i].fen++;
}
}
mergesort(1,n*2);
cout<<a[q].id;
return 0;
}
```
by Yuzilihhh @ 2023-08-05 13:53:22
666
居然发讨论版了
by hexuanhao @ 2023-08-06 10:03:49
谢谢大佬,已关注
by LiFuyin @ 2023-08-06 13:33:43