本文涉及的基础知识点

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

LeetCode2017. 网格游戏

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。
两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。每个机器人只会 向右 ((r, c) 到 (r, c + 1)) 或 向下 ((r, c) 到 (r + 1, c)) 。
游戏开始，第一个 机器人从 (0, 0) 移动到 (1, n-1) ，并收集路径上单元格的全部点数。对于路径上所有单元格 (r, c) ，途经后 grid[r][c] 会重置为 0 。然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。
第一个 机器人想要打击竞争对手，使 第二个 机器人收集到的点数 最小化 。与此相对，第二个 机器人想要 最大化 自己收集到的点数。两个机器人都发挥出自己的 最佳水平 的前提下，返回 第二个 机器人收集到的 点数 。
示例 1：
输入：grid = [[2,5,4],[1,5,1]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。
示例 2：
输入：grid = [[3,3,1],[8,5,2]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。

第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。
示例 3：
输入：grid = [[1,3,1,15],[1,3,3,1]]
输出：7
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。

第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。
提示：
grid.length == 2
n == grid[r].length
1 <= n <= 5 * 10⁴
1 <= grid[r][c] <= 10⁵

前缀和

性质一： 共移动n次。
性质二：由于只有两行，故只向下移动了一次。
两个机器人一定可以分三步：
一，向右移动了i次，i$\in$[0,n-1]。
二，向下移动一次。
三，向右移动n-1-i次。
枚举机器人一的i，令机器二的i为i1。
如果i1 < i ,则机器人二收集了grid[1][i1…i-1] 即 preSum[1][i] - min(preSum[1][i1])
如果i1 > i 则机器人二收集了grid0[0][i+1,i1] 即 max(preSum[0][i1+1]) - preSum[0][i+1])
如果i1 $==$ i ,则收集0。
注意：由于 grid[r][c]都为正数。故：
如果i1 < i ，则 i1一定是0。
如果i1 > i ,则 i1一定是n-1。
时间复杂度：O(n)

代码

核心代码

	class Solution {
		public:
			long long gridGame(vector<vector<int>>& grid) {
				const int C = grid[0].size();
				vector<vector<long long>> preSum(2, vector<long long>(1));
				for(int r = 0 ; r < 2 ;r++)
					for (const auto& n : grid[r]) {
						preSum[r].emplace_back(preSum[r].back() + n);
					}
				long long ret = LLONG_MAX;
				for (int i = 0; i < C; i++) {
					const long long cur = max(preSum[1][i], preSum[0].back() - preSum[0][i+1]);
					ret = min(ret, cur);
				}
				return ret;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {2,5,4},{1,5,1} };
			auto res = Solution().gridGame(grid);
			AssertEx(4LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {3,3,1},{8,5,2} };
			auto res = Solution().gridGame(grid);
			AssertEx(4LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,3,1,15},{1,3,3,1} };
			auto res = Solution().gridGame(grid);
			AssertEx(7LL, res);
		}