1674. Minimum Moves to Make Array Complementary

O(n+limit) time O(limit) space
这道题首先要仔细观察limit的取值范围，发现跟n是一样的，说明limit可能会影响复杂度，同时还要注意nums每个数都不超过limit，所以可以先从暴力解下手，对于每一个pair，sum变成[2, limit*2]之间任何一个数的最小步数是定值：

• [2, min(a, b)]是2个数都要减小
• [min(a, b) + 1, a + b - 1]是较大的1个数要减小
• [a + b, a + b]是两个数都不用动
• [a + b + 1, max(a, b) + limit]是较小的1个数要变大
• [max(a, b) + limit + 1, limit * 2]是2个数都要变大

暴力解需要对每一个pair都计算变成每个可能值的变化步数，复杂度过高，通过观察可以发现从2到limit*2一共只有5种可能且变化非常规律分成了5段，对应每一段的变化数是一样的，我们要做的就是把所有pair的不同变化通过某种方式累计起来，这个时候可以想到扫描线，但是单纯的扫描实际变化步数非常不方便，一个trick是利用presum来统计相邻两段区间变化步数的delta，这样就不需要维护完整的实际变化步数，可以很方便的累计到一个数组里，然后利用扫描线即可快速得到完整的累计实际变化步数

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        vector<int> f(limit * 2 + 2);
        int n = size(nums);
        for (int i = 0; i * 2 < n; ++i) {
            int a = nums[i], b = nums[n - 1 - i];
            f[2] += 2;
            --f[min(a, b) + 1];
            --f[a + b];
            ++f[a + b + 1];
            ++f[max(a, b) + limit + 1];
        }
        int res = n, cnt = 0;
        for (int i = 2; i <= limit * 2; ++i) {
            res = min(res, cnt += f[i]);
        }
        return res;
    }
};