这是 LeetCode 3449「最大化游戏分数的最小值」的 C 语言实现。解题思路这道题是第 436 场周赛的 Q4难度为 困难rating 2748核心思路是 二分查找 贪心验证 1. 二分查找对答案最大可能的最小值进行二分。下界为 0上界为最多能在 points[0] 上操作的次数乘以 points[0]。2. 贪心验证 isPossible对于给定的目标最小值 minVal判断是否能在 m 次操作内使所有位置的分数都 ≥ minVal。- 遍历每个位置计算该位置需要被访问的次数ceil(minVal / points[i])- 利用移动连续性从位置 i-1 走到 i 时如果 i-1 位置还有多余的访问次数可以传递给当前位置- 第一次到达某位置需要 1 步后续每次往返需要 2 步C 语言代码c#include stdio.h#include stdbool.h#include stdlib.h// 辅助函数判断是否能达到最小值 minVal使用不超过 m 次操作bool isPossible(int* points, int pointsSize, long long minVal, long long m) {long long moves 0; // 已使用的操作次数long long prevMoves 0; // 上一个位置剩余的操作次数for (int i 0; i pointsSize; i) {// 计算当前位置需要达到 minVal 所需的操作次数ceil(minVal / points[i])long long required (minVal points[i] - 1) / points[i];// 减去上一个位置可以传递过来的操作次数required required prevMoves ? required - prevMoves : 0;if (required 0) {// 第一次到达1步后续每次往返2步// 总共1 2*(required-1) 2*required - 1moves 2LL * required - 1;prevMoves required - 1;} else if (i 1 pointsSize) {// 当前位置已满足走到下一个位置需要1步moves 1;prevMoves 0;}if (moves m) {return false;}}return true;}// 主函数返回最大可能的最小值long long maxScore(int* points, int pointsSize, int m) {long long left 0;long long right (long long)(m 1) / 2 * points[0] 1;while (left right) {long long mid (left right 1) / 2;if (isPossible(points, pointsSize, mid, m)) {left mid;} else {right mid - 1;}}return left;}复杂度分析- 时间复杂度O(n log(m * max(points)))其中 n 是数组长度。二分查找约 log 轮每轮贪心验证 O(n)。- 空间复杂度O(1)只使用了常数额外空间。关键要点- 使用 long long 防止整数溢出m 最大可达 10^9- prevMoves 的设计是核心它记录了当前位置多余的访问次数可以传递给下一个位置体现了移动的连续性- 上界取 (m1)/2 * points[0] 是因为最优策略下在 points[0] 上最多能操作这么多次下载文件