1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <vector>
#include <algorithm>

const int M = 1'000'000'007;

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        long long sum = 0;
        int n = nums1.size();
        std::vector<std::pair<int, int>> nums(n);
        for (int i = 0; i < n; ++i) {
            int diff = std::abs(nums2[i] - nums1[i]);
            sum += diff;
            nums[i].first = nums2[i];
            nums[i].second = diff;
        }
        
        std::sort(nums.begin(), nums.end());
        std::sort(nums1.begin(), nums1.end());
        
        int max_diff = 0, new_diff;
        for (int i = 0, j = 0; i < n; ++i) {
            int num2 = nums[i].first;
            int diff = nums[i].second;
            while (j < n - 1 && nums1[j] < num2) {
                ++j;
            }
            new_diff = std::abs(nums1[j] - num2);
            if (j) {
                new_diff = std::min(new_diff, std::abs(nums1[j - 1] - num2));
            }
            max_diff = std::max(max_diff, diff - new_diff);
        }
        
        return (sum - max_diff) % M;
    }
};