我正在寻找一个快速（在复杂性方面（问题的大小可能接近2 ^ 32）和在常数方面），这不一定要计算最优解（所以一个启发式）对于特定问题，如果它产生“接近”最优的结果并且在计算时间方面具有“相当大的”优势，则可以接受。
我有一个整数直方图A：|A| = n, A[i]>0;和值R：0<R<=A[0]+...+A[n-1]。我必须尽可能均匀地在直方图上分配-R。形式上这意味着这样的东西（在正式符号中也有一些额外的信息）：我需要找到B，这样|B| = |A| && B[i] = A[i] - C[i]，其中0<=C[i]<=A[i] && C[0]+...+C[n-1] = R和C必须最小化表达式：L_2 = C[0]^2 + ... + C[n-1]^2和L_infinity = max(C[0], ..., C[n-1])。只需从公式中可以看出问题不一定具有唯一解（考虑A [0] = 1，A [1] = 1且R = 1，则B [0] = 0，B [1] ] = 1且B'[0] = 1，B'[1] = 0是最优解），可以添加一个额外的约束，例如if A[i]<A[j] then C[i]<C[j]，但在我的情况下它并不重要。天真的人可以迭代C [i]的所有可能性（R-重复组合）并找到最优解，但显然对于较大的n并不是非常快。
另一个可能的解决方案是找到q = R/n和r=R%n，然后迭代所有元素并存储diff[i] = A[i]-q，if diff[i]<=0 then r-=diff[i] && B[i] = 0 && remove A[i]，然后继续所有未移除的A [i]，将它们设置为A[i] = diff[i]，R = r和n=n-removedElementsCount。如果迭代这个过程，那么在每个步骤我们将删除至少一个元素，直到我们到达q == 0或我们只有1个元素的点，那么我们只需要从A中获得R这样的元素的A[i]-=1，因为那时R<n在q==0案例中，如果我们只有1个元素剩余（我们有0个元素的情况是微不足道的话），那么就只有A[i]-=R。由于我们每步删除至少一个元素，并且我们需要在最坏的情况下迭代(n - step)元素，因此我们具有O（（1 + ... + n））= O（n ^ 2）的复杂度。
我希望有人已经熟悉一个更好的算法，或者如果你有任何想法我会很高兴听到它们（我知道这也可以被认为是一个优化问题）。
编辑：使R为正，因此更容易阅读。
编辑2：我意识到我搞砸了优化标准。
将你的直方图变成一组(value, index)对，然后把它变成一个min heap。这个操作是O(n)。
现在你的C将采取一些值为0，减少一些最大量，其余减少1比最大量。你希望减少一切的最大数量很容易计算，它是R/n四舍五入。
现在通过堆。只要堆底部的值是< ceil(R/size of heap)，该索引处的值将设置为零，并在时间O(log(n))中从堆中删除它。一旦该循环结束，您可以将最大值和小于最大值的1分配给其余循环。
这将在O(n log(n))最糟糕的时间运行。当O(n)元素必须归零时，你将遇到最糟糕的情况。
我在O（n * log（n））时间内想出了一个非常简单的贪婪算法（如果有人设法在O（n）中解决它，尽管我很乐意听到）。
算法：
A[0],...,A[|A|-1]: A[i]>=0;整数：R0: 0<=R0<=A[0]+...+A[|A|-1]。按升序排序 - 取O（n * log（n）时间。
设置i = 0; R = R0; n = |A|; q = floor(R/n); r = R - q*n; d = q;。
if(i==|A| or R==0) goto 6.;if(i>=|A|-r) d = q + 1;4.
if(A[i]>=d)
{
R-=d;
A[i]-=d;
}
else
{
R-=A[i];
A[i] = 0;
n = |A|-(i+1);
q = floor(R/n);
d = q;
r = R - q*n;
}
i=i+1; goto 2.;if(R>0) A[|A|-1] -= R; return A;非正式解决方案最优性证明：
让n = |A|。
案例0：n==1 -> C[0] = R
案例1：n>1 && A[i]>=q && A[j]>=q+1 for j>=max(0,n-r)
最佳解决方案由C[i] = q for i<n-r && C[j] = q+1 for i>=n-r给出。假设C'[i] = C[i] + E[i]给出了另一个最优解，其中E的约束是：E[0]+...+E[m-1]=0（否则C'会违反C'[0] + ... + C'[n-1] = R），C[i]>=-E[i]（否则C'[i]会违反非负性约束），E[i] <= A[i] - C[i]（来自C'[i]<=A[i]）和E[i]<=E[j] for i<=j（来自C[i]<=C[j] for A[i]<=A[j] && A[i]<=A[j] for i<=j） ），然后：L_2' - L_2 = 2*q*(E[0]+...+E[n-r-1]) + 2*(q+1)*(E[n-r]+...+E[n-1]) + (E[0]^2 + ... + E[n-1]^2) = 2*q*0 + (E[0]^2 + ... + E[n-1]^2) + 2*(E[n-r] + ... + E[n-1]) >= 0最后的不等式是正确的，因为对于每个术语2*E[n-i], 1<=i<=r，如果它至少对于E[n-i]^2, 1<=i<=r是负的，则有相应的术语E[n-i]<-1取消它。让我们分析一下2*E[n-i] = -2的情况，显然E[n-i]^2 = 1不足以在这种情况下取消它。然而，由于E的所有元素总和为0，因此存在j!=n-i：E[j]补偿它，因为我们有E[j]^2这个词。从最后的不等式开始，L_2 <= L_2'为每个可能的解C'，这意味着C最小化L_2。很容易看到L_inf最小化也得到满足：L_inf = q + (r>0) <= L_inf' = max(q+E[0], ... , q+E[n-r-1], q+1+E[n-r], ... , q+1+E[n-1])，如果我们有一个E[i]>1 for i<n-r, or E[j]>0 for j>=n-r，我们得到更高的最大值，我们也可以永远不会减少最大值，因为E总和为0。
案例2：n>1 && there exists k: A[k]<q
在这种情况下，最佳解决方案需要C[k] = A[k]所有k: A[k]<q。让我们假设存在一个最优解C'，使C'[k]<A[k]<q -> C'[k]<q-1。存在i>=k，使C'[i]<q-1 && C'[i+1]>=q-1。假设没有这样的i，然后是C'[k] == C[n-1] < q-1和C'[0]+...+C'[n-1]<n*q-n<R，这是一个矛盾，这意味着这样的i确实存在。还有一个j>k这样C[j]>q && C[j-1]<C[j]（如果我们假设这是不真实的，我们再次得到与C总结为R的矛盾）。我们需要这些证明才能满足C[t]<=C[l] for t<=l。让我们考虑修改后的解决方案C''[t] = C'[t] for t!=i,j; and C''[i] = C'[i]+1, and C''[j] = C'[j]-1。 L_2' - L_2'' = C'[i]^2 - (C'[i]+1)^2 + C'[j]^2 - (C'[j]-1)^2 = -2*C'[i] + 2*C'[j] - 2 = 2*((C'[j]-C'[i])-1) > 2*(1-1) = 0。最后的不平等来自(C'[i]<q-1 && C'[j]>q) -> C'[j] - C'[i] > 1。如果我们增加L_2'>L_2''，我们证明了C[i]: C[i]<A[i]<q。通过诱导，最佳解决方案应该有C[l]=A[l] for all l: A[l]<q。一旦完成，人们可以归纳地继续减少问题n' = n-(i+1), R' = R - (C[0]+...+C[i]), q' = floor(R'/n'), r' = R' - q'*n', D[0] = A[i+1], ..., D[n'-1] = A[n-1]。
案例3：n>1 && A[i]>=q && A[j]<q+1 for j==max(0,n-r)
自A[k]>=A[i] for k>=i，这意味着A[i]<q+1 for i<=j。但是因为我们也有q<=A[i]这意味着A[i]==q，所以我们不能在任何C[i] : i<=j中添加任何余数。 C[i]=A[i]=q for i<j的最优性来自案例1中的证明（证明有更常见的q+1术语）。由于这个问题对于0<=i<j来说是最佳的，我们可以开始解决一个减少的问题：D[0] = A[j],...,D[n-j] = A[n-1]。
案例0,1,2,3都是可能的情况。除了明确给出解决方案的案例0和案例1之外，2和3中的解决方案将问题减少到较小的问题，其再次落入其中一个案例中。由于每个步骤都会减少问题，因此我们可以通过有限的步骤获得最终解决方案。我们也不会多次引用一个元素，这意味着O(n)时间，但我们需要O(n*log(n))进行排序，所以最后我们有O(n*log(n))算法的时间复杂度。我不确定这个问题是否可以在O(n)时间解决，但我觉得没有排序就没有办法逃脱，因为案例2和3严重依赖它，所以也许O(n*log(n))是可能的最好的复杂性实现。