AC鸭的训练分组

题目描述AC鸭准备参加一次训练营一共有 n 个训练项目第 i 个项目需要花费 ai​ 分钟。训练老师要求 AC鸭按顺序完成所有项目并且可以把这些项目分成不超过 m 组。每一组必须是连续的一段项目同一组项目在同一天完成。AC鸭不想让某一天太累所以他希望所有天数中花费时间最多的那一天尽量少。请你求出这个最小可能值。输入格式第一行两个整数 n,m表示训练项目数量和最多可以分成的组数。第二行 n 个整数第 i 个整数表示第 i 个训练项目需要花费的时间 ai​。输出格式输出一个整数表示最小可能的最大单组花费时间。样例输入数据 15 2 7 2 5 10 8输出数据 118样例解释可以分成 [7,2,5]和[10,8] 两组最大花费为 18。数据规模对于 20% 的数据1≤n≤20。对于 50% 的数据1≤n≤10001≤ai≤1000。对于 100%100% 的数据1≤n≤1000001≤m≤n1≤ai≤109。题解问题分析该问题要求将n个连续的训练项目分成不超过m组使得各组时间之和的最大值最小化。这是一个典型的最小化最大值问题通常可以通过二分查找结合贪心验证的方法解决。解决思路二分查找框架确定可能的最小最大值的范围。最小可能值为单个项目的最大时间因为至少需要包含一个项目最大可能值为所有项目时间之和即不分组的情况。验证函数对于给定的中间值mid检查是否可以将项目分成不超过m组且每组的时间之和不超过mid。如果可以则尝试更小的mid否则尝试更大的mid。算法步骤初始化二分边界左边界left为数组中的最大值右边界right为数组所有元素之和。二分查找在left right的条件下计算mid (left right) / 2并验证mid是否可行。验证函数遍历数组累加项目时间若超过mid则分组数加1并重置累加值为当前项目时间。最终检查分组数是否 m。复杂度分析时间复杂度O(n log(sum(a_i)))其中sum(a_i)是数组元素之和。二分查找的复杂度为O(log(sum(a_i)))每次验证需要O(n)时间。空间复杂度O(1)仅使用常数额外空间。C代码实现#include bits/stdc.h using namespace std; int n,m; long long a[100010] {0}; long long l 0,r 0,mid; bool p(long long s){ long long s1 0,s2 1; for(int i 1;i n;i){ s1 s1 a[i]; if(s1 s){ s1 a[i]; s2; } if(s2 m){ return 0; } } return 1; } int main(){ cinnm; for(int i 1;i n;i){ cina[i]; l max(a[i],l); r r a[i]; } while(l r){ mid (l r) / 2; if(p(mid)){ r mid; }else{ l mid 1; } } coutr; return 0; }该方法高效且易于实现适用于大规模数据。