社区讨论

WA爆零求条

P1116车厢重组参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mexz7ekb
此快照首次捕获于
2025/08/30 16:04
6 个月前
此快照最后确认于
2025/11/03 23:41
4 个月前
查看原帖
CPP
#include<iostream>
#include<vector>
using namespace std;
vector<int> a;
vector<int> b;
int cnt2=0;
void merger(int l1,int r1,int l2,int r2){
    b.clear();
    int t1=l1,t2=r2;
    while(t1<=r1 && t2<=r2){
        if(a[t1]>a[t2]){
            cnt2+=r1-t1+1;
            b.push_back(a[t2++]);
        }else{
            b.push_back(a[t1++]);
        }
    }
    while(t1<=r1) b.push_back(a[t1++]);
    while(t2<=r2) b.push_back(a[t2++]);
    for(int i=0;i<b.size();i++) a[i+l1]=b[i];
}
void merger_sort(int l,int r){
    if(l==r) return ;
    int m=(l+r)/2;
    merger_sort(l,m);
    merger_sort(m+1,r);
    merger(l,m,m+1,r);
}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int t;cin>>t;
        a.push_back(t);
    }
    merger_sort(0,n-1);
    cout<<cnt2;
    return 0;
}

回复

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

正在加载回复...