Model a probability table using 15-bit fixed probabilities
Python, score 8.682671033510566e-07, O(n * log(n))
#!/usr/bin/env python
from __future__ import division
from ast import literal_eval
from fractions import Fraction
from operator import itemgetter
from sys import argv
import fileinput

def model(hist):
    TOTAL_FINAL = 0x7fff
    TOTAL_INIT = sum(hist)
    SCALE = Fraction(TOTAL_FINAL, TOTAL_INIT)
    hist_probs = [Fraction(x, TOTAL_INIT) for x in hist]
    res = [max(int(x*SCALE),1) if x &gt; 0 else 0 for x in hist]

    adjust = TOTAL_FINAL - sum(res)
    res_probs = [Fraction(x,TOTAL_FINAL) for x in res]
    diffs = [(x-y)**2 for x,y in zip(hist_probs, res_probs)]
    d2 = [(x-y) for x,y in zip(hist_probs, res_probs)]
    if adjust &gt; 0:
        idx, vals = zip(*list(filter(lambda x:x[1]&gt;0, sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1), reverse=True))))
        i = 0
        while i &lt; adjust:
            res[idx[i%len(idx)]] += 1
            i += 1
    else:
        idx, vals = zip(*list(filter(lambda x:x[1]&lt;0,sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1)))))
        i = 0
        while i &lt; adjust:
            res[idx[i%len(idx)]] -= 1
            i += 1

    return res

if __name__ == '__main__':
    for line in fileinput.input():
        print(model(literal_eval(line)))

This takes input as a file (or sequence of files) with one Python-list-format histogram per line, with the filename(s) provided on the command line (like python prog.py hist.txt).
The general strategy here is to make a (decent) initial guess at the best probability representation, by doing integer scaling of the input histogram to 15 bits. This almost always gets the resultant list just shy of 32767 total. To adjust the probabilities, the items with the largest squared differences from the input histogram get incremented. If the result is too high initially, the largest value in the array is decreased by the excess, instead.
Time Complexity
O(n * log(n)), based on the sorting, which is the most time-consuming operation for each histogram.