optimizing unimodal functions

ternary search

template <typename F> int find_min(int l, int r, const F &f) {
    while (r - l > 3) {
        int m1 = l + ((r - l) / 3);
        int m2 = r - ((r - l) / 3);
        f(m1) > f(m2) ? l = m1 : r = m2;
    }
 
    int res = l;
    for (int i = l + 1; i <= r; i++) {
        if (f(i) < f(res)) res = i;
    }
    return res;
}

haybale distribution

• compute prefix sums for $x$, define $range(l,r)=pref[r+1]-pref[l]$
• total wasted is $\sum (a\ast (y-x_i))\forall x_i<y+\sum (b\ast (x_i-y))\forall x_i\ge y$
• where $k$ is the index of $y$, thus the count of $x_i<y$
  • left side is $a\ast (y\ast k-range(0,k-1))$
    • $a\ast \sum (y-x_i)=a\ast \sum y-\sum x_i=\dots$
  • right side is $b\ast (range(k,n-1)-y\ast (n-k))$
  • $cost(k)=left(k)+right(k)$, and $y$ is $x_k$
• find inflection point of $cost(k)$ using a search, minimum is solution
• (technically there is duplicate handling but not in scope)