package main

import (
    "fmt"
    "sort"
)

func main() {
    income := [][]int{{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}}
    ret1 := maxMoney1(income)
    fmt.Println(ret1)
    ret3 := maxMoney3(income)
    fmt.Println(ret3)
}

// 这题有贪心策略 :
// 假设一共有10个司机，思路是先让所有司机去A，得到一个总收益
// 然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益
// 这道题有贪心策略，打了我的脸
// 但是我课上提到的技巧请大家重视
// 根据数据量猜解法可以省去大量的多余分析，节省时间
// 这里感谢卢圣文同学
func maxMoney3(income [][]int) int {
    N := len(income)
    arr := make([]int, N)
    sum := 0
    for i := 0; i < N; i++ {
        arr[i] = income[i][1] - income[i][0]
        sum += income[i][0]
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] <= arr[j]
    })
    M := N >> 1
    for i := N - 1; i >= M; i-- {
        sum += arr[i]
    }
    return sum
}

// 课上的现场版本
// income -> N * 2 的矩阵 N是偶数！
// 0 [9, 13]
// 1 [45,60]
func maxMoney1(income [][]int) int {
    if len(income) < 2 || (len(income)&1) != 0 {
        return 0
    }
    N := len(income) // 司机数量一定是偶数，所以才能平分，A N /2 B N/2
    M := N >> 1      // M = N / 2 要去A区域的人
    return process1(income, 0, M)
}

// index.....所有的司机，往A和B区域分配！
// A区域还有rest个名额!
// 返回把index...司机，分配完，并且最终A和B区域同样多的情况下，index...这些司机，整体收入最大是多少！
func process1(income [][]int, index int, rest int) int {
    if index == len(income) {
        return 0
    }
    // 还剩下司机！
    if len(income)-index == rest {
        return income[index][0] + process1(income, index+1, rest-1)
    }
    if rest == 0 {
        return income[index][1] + process1(income, index+1, rest)
    }
    // 当前司机，可以去A，或者去B
    p1 := income[index][0] + process1(income, index+1, rest-1)
    p2 := income[index][1] + process1(income, index+1, rest)
    return getMax(p1, p2)
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}