为什么会RE?
  • 板块P1908 逆序对
  • 楼主qfpjm
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/12/23 17:20
  • 上次更新2023/11/5 05:46:15
查看原帖
为什么会RE?
342868
qfpjm楼主2020/12/23 17:20

只得了50分,为什么会RE?

#include <iostream>
using namespace std;
long long cnt=0;

void Merge(long long arr[],long long low, long long mid, long long high){
    //low为第1有序区的第1个元素,i指向第1个元素, mid为第1有序区的最后1个元素
    long long i = low;
    long long j = mid + 1; //mid+1为第2有序区第1个元素,j指向第1个元素
    long long k = 0;

    long long temp[high-low+1]; //temp数组暂存合并的有序序列
    while(i <= mid && j <= high){
        if(arr[i] <= arr[j]){
            //较小的先存入temp中
            temp[k++]=arr[i++];
        }
        else{
            temp[k++]=arr[j++];
            cnt+=mid-i+1;
        }

    }
    while(i<=mid){
        //若比较完之后,第一个有序区仍有剩余,则直接复制到t数组中
        temp[k++]=arr[i++];
    }
    while(j<=high){
        //同上
        temp[k++]=arr[j++];
    }

    for(i = low, k=0; i <= high; i++, k++){
        arr[i] = temp[k];//将排好序的存回arr中low到high这区间
    }

}

void MergeSort (long long arr [], long long low,long long high) {
    if(low >= high) { return; } // 终止递归的条件,子序列长度为1
    long long mid =  low + (high - low) /2;  // 取得序列中间的元素
    MergeSort(arr, low, mid);  // 对左半边递归
    MergeSort(arr, mid + 1, high);  // 对右半边递归
    Merge(arr, low, mid, high);  // 合并
}

int main()
{
    long long n;
    long long a[100001];
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    MergeSort(a, 0, n-1);  // 对数组进行归并排序

    // 输出排序后的结果
    cout<<cnt<<endl;
    return 0;
}

2020/12/23 17:20
加载中...