社区讨论
初学归并,求解为什么这个思路不对(
B3874[GESP202309 六级] 小杨的握手问题参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m03m27um
- 此快照首次捕获于
- 2024/08/21 16:47 2 年前
- 此快照最后确认于
- 2025/11/04 22:50 4 个月前
想直接转化为“正序对”求解但是不知道哪里出了问题)求调orz
CPP#include <bits/stdc++.h>
using namespace std;
int n,a[300010],b[300010];
long long ans;
void ms(int l,int r)//mergesort归并排序
{
int mid=l+(r-l)/2;
if(l==r) return;//只剩一个数就返回
ms(l,mid); ms(mid+1,r);
int i=l,j=mid+1,k=0;//i左j右指针
//ai<aj才可以握手
while(i<=mid && j<=r)//同时填入左右
{
if(a[i]<a[j])
{
ans+=mid-i+1;//计算正序对(
b[++k]=a[i++]; //填入小的数
}
else b[++k]=a[j++];
}
while(i<=mid)//右边填完了就填左边
b[++k]=a[i++]; //无法左右比较,继续填下去!
while(j<=r)//左边填完了就填右边
b[++k]=a[j++];
for(int i=l;i<=r;i++) a[i]=b[i]; //a赋值为排序后
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
ms(1,n);
//寻找正序对
cout<<ans;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...