社区讨论
告诉兄弟们一个好消息,这个题好像得用归并
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 条回复,欢迎继续交流。
正在加载回复...