怎么加速呀？各位大佬

52hertz_yh @ 2024-04-16 13:38:12

#include<bits/stdc++.h>
using namespace std;
long long a[200000000],ans,n,m;
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int j=n;j>=1;j--)
    {
        for(int i=0;i<=n-1;i++)
        {
            if(a[i]>a[i+1])
            {
                m=a[i+1];
                a[i+1]=a[i];
                a[i]=m;
                ans++;
            }
        }
    }
    cout<<ans;
}

by 0x3F @ 2024-04-16 13:43:42

@52hertz_yh 使用指令集优化即可。

by 52hertz_yh @ 2024-04-16 13:51:00

@0x3F 详细一点可以吗？ 感谢

by Weekoder @ 2024-04-16 13:58:01

@52hertz_yh 用归并排序或者树状数组。

by d909RCA @ 2024-04-16 14:08:01

@52hertz_yh 建议重构代码，O(n^2) 一般卡不过

by luuia @ 2024-04-16 14:25:56

@52hertz_yh 线段树

by 52hertz_yh @ 2024-04-17 12:46:16

@Weekoder 可以用归并吗？ 怎么用呀？ 感谢指导

by Weekoder @ 2024-04-17 13:14:53

@52hertz_yh 可以参考一下我的代码，只要在归并排序内部计数即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 5;

int n, a[N], b[N];

ll ans;

void merge(int l, int r) {
    int mid = l + r >> 1;
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++], ans += mid - i + 1;
    }
    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];
}

void MergeSort(int arr[], int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    MergeSort(arr, l, mid);
    MergeSort(arr, mid + 1, r);
    merge(l, r);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    MergeSort(a, 1, n);
    cout << ans;
    return 0;
}

by Weekoder @ 2024-04-17 13:15:15

这是较为简单的方法。