cn与えられた整数の配列です。問題は、この合計が最小化されるようにn整数の増加する配列を見つけることです。a (a[i] <= a[i+1])
abs(a[0]+c[0]) + abs(a[1]+c[1]) + ... + abs(a[n-1]+c[n-1])
// abs(x) = absolute value of x
aに出現する整数によってのみ作成された最適値が存在するため、次のcDPを使用してそれを解決できますO(n^2)。
dp[i][j]: a[i] >= j'th integer
しかし、おそらくもっと速い解決策があるはずO(n lg n)です。
更新：絶対値の合計を最小化するソリューションを追加します。二乗和を最小化する他の解決策は、誰かが興味を持っている場合に備えて、この投稿の最後にまだあります。
私は、非負の整数の配列でのみ機能するアルゴリズムから始めます。次に、任意の整数（または非整数オブジェクト）に拡張されます。
これは欲張りアルゴリズムです。整数のビット単位の表現を使用します。各配列の要素の最上位ビットから始めます（そしてしばらくの間、他のビットを無視します）。1/0のバランスを最大化する最大のプレフィックスを見つけます。次に、プレフィックスに属し、最上位ビットがゼロ（これらの値のすべてのビットがゼロ）のすべての配列値をクリアします。また、サフィックス内のゼロ以外の最上位ビットを持つすべての配列値について、他のすべてのビットを「1」に設定します。次のビットを「最上位」として使用して、このアルゴリズムをプレフィックスとサフィックスの両方に再帰的に適用します。
これにより、元の配列がセグメントに分割されます。各セグメントの中央値を見つけて、出力配列にこの中央値を入力できます。または、プレフィックスを処理するときに出力配列に対応するビットを設定し、サフィックスを処理するときにそれらをゼロのままにします。
絶対値の合計を最小化するにはサブ配列の中央値を見つける必要があるため、これはすべて機能します。この中央値を見つけながら、配列全体に対して常に1つの最上位ビットのみを使用し、他のビットに降順で値を比較できます。少し後で、サブ配列用。
詳細を説明するC++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;
}
正の整数だけでなく、任意の整数を処理するには、次の2つの方法があります。
このアルゴリズムの概要は次のとおりです。複雑さはO（N）です。
c []の先頭から開始し、可能な限り最大の平均値を持つサブ配列の検索から開始します。次に、a []内の同じ長さのサブ配列に、この平均値を入力します（最も近い整数に丸められ、否定されます）。次に、このサブアレイをa[]とc[]から削除し（つまり、a[]とc[]の先頭がサブアレイの長さだけ前方に移動すると仮定します）、このアルゴリズムをa[]とcの残りの部分に再帰的に適用します。 []。
このアルゴリズムの最も興味深い部分は、最大のサブアレイの検索です。一時配列b[]にc[]の要素の累積合計を入力します。b[0] = c[0], b[1] = b[0] + c[1], ...これで、c[]の任意の間隔の平均を次のように決定できます(b[i+m] - b[i]) / m。偶然にも、まったく同じ式（その値の最大化）によって、b[i]から曲線への接線が決定されます。これはb[]で表されます。したがって、凸包アルゴリズムを使用して、このアルゴリズムに必要なすべての最大値（およびサブ配列の境界）を一度に見つけることができます。凸包アルゴリズムは通常、2次元の点で機能し、超線形の複雑さを持っています。ただし、この場合、ポイントはすでに1次元でソートされているため、グラハムスキャンまたはモノトーンチェーンアルゴリズムはO（N）時間でタスクを実行します。これにより、アルゴリズム全体の複雑さも決まります。
