Geek asks and answers

Finding an increasing sequence a [] that minimizes sigma (abs (a [i] + c [i]))

Description of the problem

c- a given array of integers n; the problem is to find an increasing array of nintegers a (a[i] <= a[i+1])so that this amount is minimized:

abs(a[0]+c[0]) + abs(a[1]+c[1]) + ... + abs(a[n-1]+c[n-1])
// abs(x) = absolute value of x

Optimal aexists only with the help of the integers that appear in c, so we can solve it with DP in O(n^2):

dp[i][j]: a[i] >= j'th integer

But there should be a quicker solution, perhaps O(n lg n).

+3
source share
1 answer

: , . , , , , , - .

, . ( ).

. . ( ). , /. , , ( ). , , "". , " ".

. . .

, , , , , , .

++ 11, :

//g++ -std=c++0x
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;
typedef vector<unsigned> arr_t;
typedef arr_t::iterator arr_it;

void nonincreasing(arr_it array, arr_it arrayEnd, arr_it out, int bits)
{
  if (bits != -1)
  {
    int balance = 0;
    int largestBalance = -1;
    arr_it prefixEnd = array;

    for (arr_it i = array; i != arrayEnd; ++i)
    {
      int d = ((*i >> bits) & 1)? 1: -1;
      balance += d;
      if (balance > largestBalance)
      {
        balance = largestBalance;
        prefixEnd = i + 1;
      }
    }

    for (arr_it i = array; i != prefixEnd; ++i)
    {
      *(out + (i - array)) += (1 << bits);
      if (!((*i >> bits) & 1))
      {
        *i = 0;
      }
    }
    nonincreasing(array, prefixEnd, out, bits - 1);

    for (arr_it i = prefixEnd; i != arrayEnd; ++i)
    {
      if ((*i >> bits) & 1)
      {
        *i = (1 << bits) - 1;
      }
    }
    nonincreasing(prefixEnd, arrayEnd, out + (prefixEnd - array), bits - 1);
  }
}

void printArray(const arr_t& array)
{
  for (auto val: array)
    cout << setw(2) << val << ' ';
  cout << endl;
}

int main()
{
  arr_t array({12,10,10,17,6,3,9});
  arr_t out(array.size());
  printArray(array);

  nonincreasing(begin(array), end(array), begin(out), 5);
  printArray(out);

  return 0;
}

, , :

  • . , ( ). O (N log U), U - .
  • . , , . ( ). O (N log H), H - . , , ( ).

. - O (N).

, c [] . [] ( ). [] c [] ( , , [] c [] ) [] c [].

. b [] c []: b[0] = c[0], b[1] = b[0] + c[1], ... c [] : (b[i+m] - b[i]) / m. , ( ) b [i] , b []. , ( ), , Convex hull algorithm. . , Graham scan Monotone Chain O (N) , .

:

  • b [] = (c [])
  • h [] = ConvexHull (b [])
  • a [] = - (h [])

:

example

+7

More articles:


All Articles