We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Fair Cut
  5. Discussions

Fair Cut

  • jolleekin
     + 0 comments

    Here's an O(nlogn) solution based on zh2196's idea.

    .

    function fairCut(n, k, arr) {
    arr.sort((a, b) => a - b);
    if (2 * k > n) k = n - k;
    const s = (n - 2 * k) >> 1;
    const e = s + 2 * k;
    let ans = 0;
    let sum1 = 0, cnt1 = 0;
    let sum2 = 0, cnt2 = 0;
    for (let i = 0; i < n; ++i) {
        const x = arr[i];
        if (s <= i && i < e && (i & 1)) {
            sum1 += x;
            cnt1 += 1;
            ans += cnt2 * x - sum2;
        } else {
            sum2 += x;
            cnt2 += 1;
            ans += cnt1 * x - sum1;
        }
    }
    return ans;
}