社区讨论

告诉兄弟们一个好消息,这个题好像得用归并

B4361[GESP202506 四级] 排序参与者 8已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mjwzsi6p
此快照首次捕获于
2026/01/02 22:51
2 个月前
此快照最后确认于
2026/01/02 23:13
2 个月前
查看原帖

统计逆序对??

六六六,我还是第一次见统计逆序对在四级中考呢
看时间复杂度也可以
那就干吧
CPP
#include<iostream>
using namespace std;
struct node{
	int h;
	int w;
}a[3010],tmp[3010];
bool cmp(node a1,node b1){
    	return (a1.h==b1.h)?a1.w>=b1.w:a1.h>b1.h;//这个>=必须带!!!
}
int ans=0;
void msort(int l,int r){
	if(l<r){
		int mid=(l+r)/2;
		msort(l,mid);
		msort(mid+1,r);
		int i=l,j=mid+1,k=0;
		while(i<=mid&&j<=r){
			if(cmp(a[i],a[j])){
				tmp[k]=a[i++];
			}else{
				ans+=mid-i+1;
				tmp[k]=a[j++];
			}
			k++;
		}
		while(i<=mid){
			tmp[k]=a[i++];
			k++;
		}
		while(j<=r){
			tmp[k]=a[j++];
			k++;
		}
		for(i=l,j=0;j<k;i++,j++){
			a[i] = tmp[j];
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d",&a[i].h,&a[i].w);
	}
	msort(0,n-1);
	printf("%d",ans);
	return 0;
}
不知道那些85分的是不是TLE了

回复

7 条回复,欢迎继续交流。

正在加载回复...