悬赏关注
  • 板块灌水区
  • 楼主hkl99
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/10/21 12:34
  • 上次更新2024/10/21 15:57:34
查看原帖
悬赏关注
770439
hkl99楼主2024/10/21 12:34

P1309 [NOIP2011 普及组] 瑞士轮

用了归并排序,为啥写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;
}

2024/10/21 12:34
加载中...