qfpjm @ 2020-12-23 17:20:59
只得了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;
}
by 幻影星坚强 @ 2020-12-23 17:34:49
仔细看看数据范围
by qfpjm @ 2021-01-01 15:43:04
@幻影星坚强 已过