LeetCode1478. 安排邮筒

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
答案保证在 32 位有符号整数范围以内。
示例 1：
输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：
输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：
输入：houses = [7,4,6,1], k = 1
输出：8
示例 4：
输入：houses = [3,6,14,10], k = 4
输出：0
提示：
n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10⁴
1 <= k <= n
数组 houses 中的整数互不相同。

动态规划

原理

houser[i,j]之间安装邮筒，安装到正中间的房子是最优解。
a,假定房子数是奇数，假定共有2n+1个房子。假定左边有i1个房子，右边有i2个房子。如果i1 < i2，则右移可以缩短距离;i1 > i2，则左移可以缩短距离。如果邮筒不在屋子上，则i1永远不会等于i2。i1==i2，则必定在最中间的屋子。i+(j-i)/2。
b，屋子为偶数，在中间的两坐房子之间，才会让i1和i2。其实中间两间房子的任何一间房子都可以。
可以统一为：i+(j-i)/2
确切的说： { 左边及本身的房子数小于右边的房子数，右移动。 右边及本身的房子数小于左边的房子数，左移动。 \begin{cases} 左边及本身的房子数小于右边的房子数，右移动。\\ 右边及本身的房子数小于左边的房子数，左移动。\\ \end{cases} {左边及本身的房子数小于右边的房子数，右移动。右边及本身的房子数小于左边的房子数，左移动。​ $\to$ 稳定状态下，必须
{ i 1 > = i 2 , i 1 < = i 2 → i 1 = = i 2 邮筒不在房子上 i 1 + 1 > = i 2 , i 2 + 1 > = i 1 → a b s ( i 1 − i 2 ) < = 1 邮筒在房子上 → \begin{cases} i1 >=i2,i1 <=i2 \rightarrow i1==i2 & 邮筒不在房子上 \\ i1+1>=i2,i2+1 >= i1 \rightarrow abs(i1-i2)<=1 & 邮筒在房子上\\ \end{cases} \rightarrow {i1>=i2,i1<=i2→i1==i2i1+1>=i2,i2+1>=i1→abs(i1−i2)<=1​邮筒不在房子上邮筒在房子上​→
如果房子数量是奇数
{ 邮筒不在房子上 i 1 = = i 2 → ( i 1 + i 2 ) 是偶数 → 房子总数是奇数矛盾 邮筒在房子上且 i 1 等于 i 2 正中间的房子 邮筒在房子上且 i 1 和 i 2 相差 1 假定 11 + 1 = i 2 → i 1 + i 2 + 1 是偶数，和总数是奇数矛盾 → \begin{cases} 邮筒不在房子上& i1==i2 \rightarrow (i1+i2)是偶数 \rightarrow 房子总数是奇数矛盾 \\ 邮筒在房子上且i1等于i2 & 正中间的房子 \\ 邮筒在房子上且i1和i2相差1 & 假定11+1=i2 \rightarrow i1+i2+1是偶数，和总数是奇数矛盾 \\ \end{cases} \rightarrow ⎩ ⎨ ⎧​邮筒不在房子上邮筒在房子上且i1等于i2邮筒在房子上且i1和i2相差1​i1==i2→(i1+i2)是偶数→房子总数是奇数矛盾正中间的房子假定11+1=i2→i1+i2+1是偶数，和总数是奇数矛盾​→ 如果房子的数量是奇数则只能安装在最中间。
如果房子数量是偶数
{ 邮筒不在房子上 i 1 = = i 2 → 中间两间房子的空地 邮筒在房子上且 i 1 等于 i 2 i 1 + i 2 + 1 是奇数，与假设矛盾 邮筒在房子上且 i 1 和 i 2 相差 1 中间任意两间房子 → \begin{cases} 邮筒不在房子上& i1==i2 \rightarrow 中间两间房子的空地 \\ 邮筒在房子上且i1等于i2 & i1+i2+1是奇数，与假设矛盾 \\ 邮筒在房子上且i1和i2相差1 & 中间任意两间房子 \\ \end{cases} \rightarrow ⎩ ⎨ ⎧​邮筒不在房子上邮筒在房子上且i1等于i2邮筒在房子上且i1和i2相差1​i1==i2→中间两间房子的空地i1+i2+1是奇数，与假设矛盾中间任意两间房子​→
如果房间数是偶数，则中间的两间房子及之间的空地都是最优解。

预处理

vDis[i][j] ，记录一个邮筒到house[i,j]的距离之和。houses要先排序。

动态规划的状态表示

dp[i][j] 表示 j个邮筒支持前i栋房最小距离。

动态规划的状态方程

通过前者状态更新后置状态。
k = 1 i + k < = h o u s e s . l e n g t h \Large_{k=1}^{i+k <= houses.length} k=1i+k<=houses.length​ pre[i+k][j+1] = min( $\cdots$,pre[i][j]+vDis[$\cdots$])

动态规划的初始值

dp[0][0]=0 ，其它INT_MAX，表示非法值。

动态规划的填表顺序

i从小到大,j从小到大。

动态规划的返回值

dp.back()[k]

代码

核心代码

class Solution {
public:
	int minDistance(vector<int>& houses, int K) {
		m_c = houses.size();
		sort(houses.begin(), houses.end());
		vector<vector<int>> vDis(m_c, vector<int>(m_c));
		for (int center = 0; center < m_c; center++)
		{
			{
				int iDis = 0;
				for (int i = center, j = center; (i >= 0) && (j < m_c); i--, j++)
				{
					iDis += houses[j] - houses[i];
					vDis[i][j] = iDis;
				}
			}
			{
				int iDis = 0;
				for (int i = center, j = center + 1; (i >= 0) && (j < m_c); i--, j++)
				{
					iDis += houses[j] - houses[i];
					vDis[i][j] = iDis;
				}
			}
		}
		vector<vector<int>> dp(m_c + 1, vector<int>(K + 1, INT_MAX));
		dp[0][0] = 0;
		for (int i = 0; i <= m_c; i++)
		{
			for (int j = 0; j < K; j++)
			{
				if (INT_MAX == dp[i][j])
				{
					continue;
				}
				for (int m = 1; m + i <= m_c; m++)
				{
					dp[m + i][j + 1] = min(dp[m + i][j + 1],dp[i][j]+vDis[i][i+m-1]);
				}
			}
		}
		return dp.back().back();
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<int> houses;
	int k;
	{
		Solution sln;
		houses = { 7,4,6,1 };
		k = 1;
		auto res = sln.minDistance(houses, k);
		Assert(8, res);
	}
	{
		Solution sln;
		houses = { 1, 4, 8, 10, 20 };
		k = 3;
		auto res = sln.minDistance(houses, k);
		Assert(5, res);
	}
	{
		Solution sln;
		houses = { 2,3,5,12,18 };
		k = 2;
		auto res = sln.minDistance(houses, k);
		Assert(9, res);
	}
	
	{
		Solution sln;
		houses = { 3,6,14,10 };
		k = 4;
		auto res = sln.minDistance(houses, k);
		Assert(0, res);
	}
}

2023年2月版

class Solution {
public:
int minDistance(vector& houses, int k) {
const int iNotMay = 1000 * 1000 * 10;
std::sort(houses.begin(), houses.end());
m_c = houses.size();
vector pre(m_c);
for (int i = 0; i < m_c; i++)
{
pre[i] = Cost(houses, 0, i + 1);
}
for (int iK = 2; iK <= k; iK++)
{
vector dp(m_c, iNotMay);
for (int iHouse = 0; iHouse < houses.size(); iHouse++)
{
for (int pr = 0; pr < iHouse; pr++)
{
if (iNotMay == pre[pr])
{
continue;
}
dp[iHouse] = min(dp[iHouse], pre[pr] + Cost(houses, pr+1, iHouse + 1));
}
}
pre.swap(dp);
}
return pre.back();
}
int Cost(const vector& houses,int left, int r)
{
int iCost = 0;
int iMean = houses[left + (r - left) / 2];
for (int i = left; i < r; i++)
{
iCost += abs(houses[i] - iMean);
}
return iCost;
}
int m_c;
};

2023年7月版

class Solution {
public:
int minDistance(vector& houses, int k) {
m_c = houses.size();
sort(houses.begin(), houses.end());
vector<vector> vCost(m_c, vector(m_c));
for(int i= 0 ;i < m_c; i++ )
for (int j = i+1; j < m_c; j++)
{
int iMidValue = houses[i] + (houses[j] - houses[i]) / 2;
int cost = 0;
int k = i+1;
for (; houses[k] <= iMidValue; k++)
{
cost += houses[k] - houses[i];
}
for (; k < j; k++)
{
cost += houses[j] - houses[k];
}
vCost[i][j] = cost;
}
const int iNotMay = 1000 * 1000 * 10;
vector<vector> dp(m_c + 1, vector(k + 1, iNotMay));
dp[0][0] = 0;
dp[0][1] = 0;
vector vBegin(m_c);
{
int iSum = 0;
for (int i = 1; i < m_c; i++)
{
iSum += (houses[i] - houses[i - 1]) * i;
vBegin[i] = iSum;
}
}
for (int i = 1; i < m_c; i++)
{
for (int prePos = 0; prePos < i; prePos++)
{
for (int preK = 0; preK < k; preK++)
{
if (iNotMay == dp[prePos][preK])
{
continue;
}
if (0 == preK)
{
dp[i][preK + 1] = vBegin[i];
continue;
}
dp[i][preK + 1] = min(dp[i][preK + 1],dp[prePos][preK] + vCost[prePos][i]);
}
}
}
vector vEnd(m_c);
{
int iSum = 0;
for (int i = m_c - 2; i >= 0; i–)
{
iSum += (houses[i + 1] - houses[i]) * (m_c - 1 - i);
vEnd[i] = iSum;
}
}
int iRet = iNotMay;
for (int i = k-1; i < m_c; i++)
{
iRet = min(iRet, dp[i][k] +vEnd[i]);
}
return iRet;
}
int m_c;
};