C++前缀和算法的应用：摘水果 原理源码测试用例

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode2106摘水果

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
返回你可以摘到水果的 最大总数 。
示例 1：
输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：

• 向右移动到位置 6 ，摘到 3 个水果
• 向右移动到位置 8 ，摘到 6 个水果
  移动 3 步，共摘到 3 + 6 = 9 个水果
  示例 2：
  输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
  输出：14
  解释：
  可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
  最佳路线为：
• 在初始位置 5 ，摘到 7 个水果
• 向左移动到位置 4 ，摘到 1 个水果
• 向右移动到位置 6 ，摘到 2 个水果
• 向右移动到位置 7 ，摘到 4 个水果
  移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果
  示例 3：
  输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
  输出：0
  解释：
  最多可以移动 k = 2 步，无法到达任一有水果的地方

参数范围：
1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）
1 <= amounti <= 104
0 <= k <= 2 * 105

分析

原理

只需要左移（右移）一次。假定左移了两次，分别移动了x1,x2,假定x1 分四种情况：
一，左移到底。
二，先左移，后右移。
三，右移到底。
四，先右移，再左移。
一是四的特殊请，三是二的特殊情况。

步骤

一，先获取前缀和。
二，枚举左移。右移为0或负数，忽视，因为劣于左移到底。k为0是，此条不符合。
三，枚举右移。

注意

坐标无限，但前缀和有限[0,iMaxPos]。

变量解释

代码

核心代码

class Solution {
public:
int maxTotalFruits(vector& fruits, int startPos, int k) {
const int iMaxPos = fruits.back()[0];
vector vNum(iMaxPos + 1);
for (const auto&v : fruits)
{
vNum[v[0]] = v[1];
}
vector vSum = { 0 };//vSum[i]记录[0,i)草莓的总数量
for (int i =0; i <= iMaxPos; i++)
{
vSum.emplace_back(vSum.back() + vNum[i]);
}

	int iRet = 0;
	for (int iMoveLeft = 0; iMoveLeft <= k / 2; iMoveLeft++)
	{//先左后右
		const int iMoveRight = k - iMoveLeft * 2;
		if (iMoveRight < 0)
		{
			continue;
		}
		const int left = max(0, startPos - iMoveLeft);
		if (left > iMaxPos)
		{
			continue;
		}
		const int right = min(iMaxPos, startPos + iMoveRight);
		//可收集[left,right+1)的草莓
		const int cur = vSum[right + 1] - vSum[left];
		iRet = max(iRet, cur);
	}

	for (int iMoveRight = 0; iMoveRight <= k / 2; iMoveRight++)
	{//先左后右
		const int iMoveLeft = k - iMoveRight * 2;
		if (iMoveLeft < 0)
		{
			continue;
		}
		const int left = max(0, startPos - iMoveLeft);
		if (left > iMaxPos)
		{
			continue;
		}
		const int right = min(iMaxPos, startPos + iMoveRight);
		//可收集[left,right+1)的草莓
		const int cur = vSum[right + 1] - vSum[left];
		iRet = max(iRet, cur);
	}
	return iRet;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

};

测试用例

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

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

int main()
{
Solution slu;
vector fruits;
int startPos = 0;
int k = 0;
int res;

fruits = {{2, 8}, {6, 3}, {8, 6}};
startPos =5 ;
k =4 ;
res = slu.maxTotalFruits(fruits, startPos, k);
Assert(9, res);

fruits = {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}};
startPos = 5;
k = 4;
res = slu.maxTotalFruits(fruits, startPos, k);
Assert(14, res);

fruits = { {0,10000} };
startPos = 20000;
k = 20000;
res = slu.maxTotalFruits(fruits, startPos, k);
Assert(10000, res);

fruits = { {20000,10000} };
startPos = 20000;
k = 0;
res = slu.maxTotalFruits(fruits, startPos, k);
Assert(10000, res);


//CConsole::Out(res);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

}

2023年3月旧代码

class Solution {
public:
int maxTotalFruits(vector& fruits, int startPos, int k) {
m_c = fruits.size();
int iMaxLeftIndex = std::lower_bound(fruits.begin(), fruits.end(),startPos, [](const vector& v, int i)
{
return v[0] < i;
}) - fruits.begin() - 1;
std::map mLeftMoveNum;
for (int i = iMaxLeftIndex ; (i >= 0) && (startPos - fruits[i][0] <= k); i–)
{
const int iLeftMove = startPos - fruits[i][0];
mLeftMoveNum[iLeftMove] = fruits[i][1] + (mLeftMoveNum.empty() ? 0 : mLeftMoveNum.rbegin()->second);
}
int iMinRightIndex = iMaxLeftIndex + 1;
int iRet = 0;
if ((iMinRightIndex < m_c) && (fruits[iMinRightIndex][0] == startPos))
{
iRet += fruits[iMinRightIndex][1];
iMinRightIndex++;
}
std::map mRightMoveNum;
for (int i = iMinRightIndex; (i < m_c) && (fruits[i][0] - startPos <= k); i++)
{
const int iRightMove = fruits[i][0] - startPos;
mRightMoveNum[iRightMove] = fruits[i][1] + (mRightMoveNum.empty() ? 0 : mRightMoveNum.rbegin()->second);
}

	 int iMaxExcludeStart = 0;
	 for (int left = 0; left <= k / 2; left++)
	 {
		 const int right = k - left * 2;
		 int iCur = 0;
		 {
			 auto itLeft = mLeftMoveNum.upper_bound(left);
			 if (mLeftMoveNum.begin() != itLeft)
			 {
				 iCur += (--itLeft)->second;
			 }
		 }
		 {
			 auto itRight = mRightMoveNum.upper_bound(right);
			 if (mRightMoveNum.begin() != itRight)
			 {
				 iCur += (--itRight)->second;
			 }
		 }
		 iMaxExcludeStart = max(iMaxExcludeStart, iCur);
	 }
	 for (int right = 0; right <= k / 2; right++)
	 {
		 const int left = k - right * 2;
		 int iCur = 0;
		 {
			 auto itLeft = mLeftMoveNum.upper_bound(left);
			 if (mLeftMoveNum.begin() != itLeft)
			 {
				 iCur += (--itLeft)->second;
			 }
		 }
		 {
			 auto itRight = mRightMoveNum.upper_bound(right);
			 if (mRightMoveNum.begin() != itRight)
			 {
				 iCur += (--itRight)->second;
			 }
		 }
		 iMaxExcludeStart = max(iMaxExcludeStart, iCur);
	 }
	 iRet += iMaxExcludeStart;
	 return iRet;
 }
 int m_c;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

| 鄙人想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17