2 条题解

  • 0
    @ 2023-3-26 16:17:05

    以下是询问chatGPT得到的Accepted答案

    #include <vector>
    
    using namespace std;
    
    long long merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> tmp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        long long count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
                count += mid - i + 1;
            }
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        for (k = 0, i = left; i <= right; ++i, ++k) {
            nums[i] = tmp[k];
        }
        return count;
    }
    
    long long merge_sort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) >> 1;
        long long count_left = merge_sort(nums, left, mid);
        long long count_right = merge_sort(nums, mid + 1, right);
        long long count = merge(nums, left, mid, right);
        return count_left + count_right + count;
    }
    
    int main() {
        int n;
        cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }
        cout << merge_sort(nums, 0, n - 1) << endl;
        return 0;
    }
    

    信息

    ID
    435
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    70
    已通过
    23
    上传者