arrays - 对于数组 A [0...N-1]，在没有两个非零元素的差 > M 之前，我必须将元素递减多少次？

Question

大小为 N A [0...N-1] 的数组包含一些正整数。我需要递减某个元素的最少次数是多少，这样就没有两个元素(A[i] 和 A[j]，i != j，A[i]>0，A[j]>0)差异 > M ?

到目前为止我的方法:

for(int i = N-1;i>=0;i--)
{
    for(int j = 0;j<=i-1;j++)
    {
        while(A[i]-A[j]>M)
        {
            A[i]--;
            ans++;
        }

    }

}

但是，这不是正确的解决方案。例如，

A = {3 2 1} 和 M = 0

最佳解决方案是将 A[2] 递减一次，将 A[0] 递减一次。

这使得数组 A = {2 2 0}

因为，A[2] = 0 我们可以忽略它，因为我们只担心非零元素。

但是，这段代码产生 ans = 3。

有什么解决方案吗？

Answer 1

这可以在 O(N log N) 时间内完成，如果数组已预排序，则为 O(N) 时间。

在伪代码中:

Given:  A : array of ints, M = max difference

sort(A); //O(N log N) time

int start = end = 0;  //this is a subsequence that we will move though the array

int sum_before = 0; //sum of all elements before our subsequence
int sum_after = sum_all(A); // sum of all elements after our subsequence -- O(N) time

int best_answer = sum_after; //we could always decrement everything to zero

for (start=0; start < A.length; ++start )
{
   int maxval = A[start]+M;  //A is sorted, so this never gets smaller

   //extend end to find the longest subsequence starting
   //at A[start] that we don't have to change

   while( end < A.length && A[end]<=maxval)
   {
       //we can increment end at most A.length times, so
       //this loop is O(N) in total for all iterations

       sum_after-=A[end];
       ++end;
   }

   //if we leave everything between start and end unchanged
   //the we'll need to decrement everything before to zero and
   //everything after to maxval

   int current_answer = sum_before + sum_after - (A.length - end)*maxval;

   best_answer = min(best_answer, current_answer);

   //next subsequence excludes A[start] -- it goes into the "before" sum
   sum_before+=A[start];
}