用了归并排序,为啥写TLE了
代码:
#include<bits/stdc++.h>
using namespace std;
int n,r,q;
struct node {
int id;
int s,w;
} a[200010],b[200010];
void merge(int l,int r) {
if(l==r) {return;}
int mid=(l+r)>>1;
merge(l,mid);
merge(mid+1,r);
int len=(l-r+1);
memset(b,0,sizeof(b));
int i=l;
int j=mid+1;
int k=1;
while(i<=mid&&j<=r) {
if(a[i].s>a[j].s||(a[i].s==a[j].s&&a[i].id<a[j].id)) {
b[k]=a[i];
i++;
} else {
b[k]=a[j];
j++;
}
k++;
}
while(i<=mid) {
b[k]=a[i];
k++;
i++;
}
while(j<=r) {
b[k]=a[j];
j++;
k++;
}
for(int z=l; z<=r; z++) {
a[z]=b[z-l+1];
}
}
int main() {
scanf("%d%d%d",&n,&r,&q);
n*=2;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i].s);
a[i].id=i;
}
for(int i=1; i<=n; i++) {
scanf("%d",&a[i].w);
}
for(int i=1; i<=r; i++) {
merge(1,n);
for(int i=2; i<=n; i+=2) {
if(a[i].w>a[i-1].w) {
a[i].s++;
} else {
a[i-1].s++;
}
}
}
merge(1,n);
printf("%d",a[q].id);
return 0;
}