数组划分最小最大和 - C++11 实现 - 常规

{"title":"数组划分最小最大和 - C++11 实现", "description":"给定一个包含n个正整数的数组，将数组划分为k个子数组，目标是使子数组中的和的最大值尽可能小。本示例使用C++11实现该算法，并提供代码解释和示例。", "keywords":"数组划分, 最小最大和, 子数组, C++11, 算法, 代码示例", "content":"#include \n#include \n#include \nusing namespace std;\n\nint main() {\n int n, k;\n cin >> n >> k;\n \n vector nums(n);\n for (int i = 0; i < n; i++) {\n cin >> nums[i];\n }\n \n int left = *max_element(nums.begin(), nums.end());\n int right = accumulate(nums.begin(), nums.end(), 0);\n \n while (left < right) {\n int mid = left + (right - left) / 2;\n \n int count = 1;\n int sum = 0;\n for (int i = 0; i < n; i++) {\n sum += nums[i];\n if (sum > mid) {\n sum = nums[i];\n count++;\n }\n }\n \n if (count > k) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n \n cout << left << endl;\n \n return 0;\n}