Nem*_*emo 15
好吧,我想我可以在O(n log n)中完成.如果最初对数组进行排序,我只能执行O(n).
首先,注意观察,你可以置换a,b,c但是你喜欢不改变表达式的值.因此,让我们x是最小的a,b,c,让我们y三个中间; 让我们z成为最大的.然后请注意表达式等于2*(z-x).(编辑:这很容易看到......一旦你按顺序得到三个数字x < y < z,总和就是(y-x) + (z-y) + (z-x)等于2*(z-x))
因此,我们真正想要做的就是找到三个数字,使得外部两个尽可能地靠近在一起,另一个数字"夹在"它们之间.
因此,首先在O(n log n)中对所有三个数组进行排序.维护每个数组的索引; 调用这些i,j和k.将所有三个初始化为零.无论哪个指数指向最小值,都要增加该指数.也就是说,如果A[i]小于B[j]和C[k],则增加i; 如果B[j]是最小的,增量j; if C[k]最小,增量k.重复,跟踪|A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]|整个时间.你在这次游行中观察到的最小值是你的答案.(当三个中最小的一个位于其数组的末尾时,请停止,因为已完成.)
在每个步骤中,您只需向一个索引添加一个; 但是n在结束之前你只能为每个阵列做这个时间.所以这是大多数3*n步骤,即O(n),小于O(n log n),意味着总时间为O(n log n).(或者只是O(n),如果你可以假设数组已经排序.)
证明这个作品的素描:假设A[I],B[J],C[K]是a,b,c形成实际的答案; 即,他们有最低限度|a-b|+|b-c|+|c-a|.进一步假设a> b> c; 其他案例的证据是对称的.
引理:在我们游行期间,我们不会增加j过去,J直到我们增加k过去K.证明:我们总是递增最小元素的索引,以及何时k <= K,B[J] > C[k].所以当j=J和k <= K,B[j]并不是最小的元素,所以我们不增加j.
现在假设我们在达到之前增加k过去.在我们执行该增量之前,事情会是什么样子？嗯,是那个时刻三个中最小的,因为我们即将增加. 小于或等于,因为并被排序.最后,因为(通过我们的引理),所以也不到.总之,这意味着我们在这一刻总和法ABS-DIFF是少比,这是一个矛盾.KiIC[k]kA[i]A[I]i < IAj <= Jk <= KB[j]A[I]2*(c-a)
因此,我们不增加k过去K,直到i到达I.因此,在我们的行军过程中的一些点i=I和k=K.通过我们的引理,此时j小于或等于J.所以在这一点上,要么B[j]小于其他两个并且j会增加; 或者B[j]介于另外两个之间,我们的总和是正确的2*(A[i]-C[k]),这是正确的答案.
这个证据很草率; 特别是,它没有明确地考虑其中一个或多个的情况下a,b,c是相等的.但我认为细节很容易解决.