一些模数恶作剧

Question

我正在 LeetCode 上解决一个问题：

You are given two positive integer arrays nums1 and nums2, both of length n.The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed). You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference. Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo (10^9 + 7). For Input: nums1 = [1,7,5], nums2 = [2,3,5], Output: 3.

我想出的代码如下：

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        if(nums1==nums2) return 0;

        long long MOD=(int)1e9+7;

        set<long long> s(begin(nums1),end(nums1));
        
        long long diff=0ll, res=LLONG_MAX;
        for(int i=0; i<nums1.size(); i++)
            diff=(diff%MOD+(abs(nums1[i]-nums2[i]))%MOD)%MOD;
        
        for(int i=0; i<nums2.size(); i++) {
            long long curr=nums2[i];
            auto lb=s.lower_bound(curr);

            if(lb!=s.begin()) {
                auto p=prev(lb);
                long long prevElement=*p;
                long long currsum=diff;

                currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;
                currsum=(currsum%MOD+abs(curr-prevElement)%MOD)%MOD;

                res=min(res, currsum);
            }

            if(lb!=s.end()) {
                long long nextElement=*lb;
                long long currsum=diff;

                currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;
                currsum=(currsum%MOD+(abs(curr-nextElement))%MOD)%MOD;

                res=min(res, currsum);
            }
        }
        
        return res;
    }
};

这适用于 50/51 个测试用例，但在最后一个具有较大值的测试用例上，一些取模 hijinkery 破坏了它。我这样做的原因：

currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;

是因为模的分配属性:(a + b) % c = ((a % c) + (b % c)) % c.

我错过了什么？

Answer 1

这个问题是模运算的一个常见错误，令人惊讶的是，它与整数溢出无关（通常是这种情况），而仅仅是 顺序属性与模数不能很好地混合的结果.

你说分配式属性、(a + b) % c = ((a % c) + (b % c)) % c应该让你在方程中取模。当结果相互比较时，这不再是真的。让我们看一个问题更简单的小例子：

Given two arrays A and B, find the array with the smallest sum,
 and return its sum modulo 9.

A = [2, 8]
B = [1, 1]

现在答案应该是数组B，其和为2，小于10。如果只在最后取模，则正确答案为：

sum(A) = 10
sum(B) = 2

sum(B) < sum(A), so return (2 % 9) == 2

但是如果你在中间进行取模：

sum(A) % 9 == 1
sum(B) % 9 == 2

sum(A) % 9 < sum(B) % 9, so you return (1 % 9) == 1

由于此处的约束意味着您的总和不能溢出 long long int，因此您的问题已通过 仅在最后执行一次模运算得到解决，在 return 语句中.

一般来说，您想要（最小和）模 p 而不是最小（和模 p）的问题要求您不对中间结果执行模除法：您必须使用足够大的整数类型来比较真实值（或至少有一种比较真实值的方法）。

一些模数恶作剧

Some modulo hijinkery

c++

algorithm

modulo