首页 - 通讯 - 2021-04-30：一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示居民点的一维坐标，再给定一个正数 num，表示邮局数量。选择num个居民点建立num个邮局，使

2021-04-30：一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示居民点的一维坐标，再给定一个正数 num，表示邮局数量。选择num个居民点建立num个邮局，使

2023-09-05 16:14

-->

2021-04-30：一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示居民点的一维坐标，再给定一个正数 num，表示邮局数量。选择num个居民点建立num个邮局，使所有的居民点到最近邮局的总距离最短，返回最短的总距离。【举例】arr=[1,2,3,4,5,1000]，num=2。第一个邮局建立在 3 位置，第二个邮局建立在 1000 位置。那么 1 位置到邮局的距离为 2， 2 位置到邮局距离为 1，3 位置到邮局的距离为 0，4 位置到邮局的距离为 1， 5 位置到邮局的距离为 2，1000 位置到邮局的距离为 0。这种方案下的总距离为 6，其他任何方案的总距离都不会比该方案的总距离更短，所以返回6。

福大大答案2021-04-30：

动态规划。

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math"

)

func main() {

    arr := []int{1, 2, 3, 4, 5, 1000}

    num := 2

    ret := min1(arr, num)

    fmt.Println(ret)

    //ret = min2(arr, num)

    //fmt.Println(ret)

}

func min1(arr []int, num int) int {

    if num < 1 || len(arr) < num {

        return 0

    }

    N := len(arr)

    w := make([][]int, N+1)

    for i := 0; i < N+1; i++ {

        w[i] = make([]int, N+1)

    }

    for L := 0; L < N; L++ {

        for R := L + 1; R < N; R++ {

            w[L][R] = w[L][R-1] + arr[R] - arr[(L+R)>>1]

        }

    }

    dp := make([][]int, N)

    for i := 0; i < N; i++ {

        dp[i] = make([]int, num+1)

    }

    for i := 0; i < N; i++ {

        dp[i][1] = w[0][i]

    }

    for i := 1; i < N; i++ {

        for j := 2; j <= getMin(i, num); j++ {

            ans := math.MaxInt32

            for k := 0; k <= i; k++ {

                ans = getMin(ans, dp[k][j-1]+w[k+1][i])

            }

            dp[i][j] = ans

        }

    }

    return dp[N-1][num]

}

func getMin(a int, b int) int {

    if a < b {

        return a

    } else {

        return b

    }

}

//func min2(arr []int, num int) int {

//  if num < 1 || len(arr) < num {

//      return 0

//  }

//  N := len(arr)

//  w := make([][]int, N+1)

//  for i := 0; i < N+1; i++ {

//      w[i] = make([]int, N+1)

//  }

//  for L := 0; L < N; L++ {

//      for R := L + 1; R < N; R++ {

//          w[L][R] = w[L][R-1] + arr[R] - arr[(L+R)>>1]

//      }

//  }

//

//  dp := make([][]int, N)

//  for i := 0; i < N; i++ {

//      dp[i] = make([]int, num+1)

//  }

//

//  best := make([][]int, N)

//  for i := 0; i < N; i++ {

//      best[i] = make([]int, num+1)

//  }

//  for i := 0; i < N; i++ {

//      dp[i][1] = w[0][i]

//      best[i][1] = -1

//  }

//  for j := 2; j <= num; j++ {

//      for i := N - 1; i >= j; i-- {

//          down := best[i][j-1]

//          up := twoSelectOne(i == N-1, N-1, best[i+1][j])

//          ans := math.MaxInt32

//          bestChoose := -1

//          for leftEnd := down; leftEnd <= up; leftEnd++ {

//              leftCost := twoSelectOne(leftEnd == -1, 0, dp[leftEnd][j-1])

//              rightCost := twoSelectOne(leftEnd == i, 0, w[leftEnd+1][i])

//              cur := leftCost + rightCost

//              if cur <= ans {

//                  ans = cur

//                  bestChoose = leftEnd

//              }

//          }

//          dp[i][j] = ans

//          best[i][j] = bestChoose

//      }

//  }

//  return dp[N-1][num]

//}

func twoSelectOne(isSelectFirst bool, a int, b int) int {

    if isSelectFirst {

        return a

    } else {

        return b

    }

}