AC鸭的训练分组

题目描述

AC鸭准备参加一次训练营，一共有 n 个训练项目，第 i 个项目需要花费 ai​ 分钟。

训练老师要求 AC鸭按顺序完成所有项目，并且可以把这些项目分成不超过 m 组。每一组必须是连续的一段项目，同一组项目在同一天完成。

AC鸭不想让某一天太累，所以他希望所有天数中，花费时间最多的那一天尽量少。

请你求出这个最小可能值。

输入格式

第一行两个整数 n,m表示训练项目数量和最多可以分成的组数。

第二行 n 个整数，第 i 个整数表示第 i 个训练项目需要花费的时间 ai​。

输出格式

输出一个整数，表示最小可能的最大单组花费时间。

样例

输入数据 1

5 2 7 2 5 10 8

输出数据 1

18

样例解释

可以分成 [7,2,5]和[10,8] 两组，最大花费为 18。

数据规模

对于 20% 的数据，1≤n≤20。

对于 50% 的数据，1≤n≤1000，1≤ai≤1000。

对于 100%100% 的数据，1≤n≤100000，1≤m≤n，1≤ai≤109。

题解

问题分析

该问题要求将n个连续的训练项目分成不超过m组，使得各组时间之和的最大值最小化。这是一个典型的最小化最大值问题，通常可以通过二分查找结合贪心验证的方法解决。

解决思路

1. 二分查找框架：确定可能的最小最大值的范围。最小可能值为单个项目的最大时间（因为至少需要包含一个项目），最大可能值为所有项目时间之和（即不分组的情况）。
2. 验证函数：对于给定的中间值mid，检查是否可以将项目分成不超过m组，且每组的时间之和不超过mid。如果可以，则尝试更小的mid；否则，尝试更大的mid。

算法步骤

1. 初始化二分边界：左边界left为数组中的最大值，右边界right为数组所有元素之和。
2. 二分查找：在left <= right的条件下，计算mid = (left + right) / 2，并验证mid是否可行。
3. 验证函数：遍历数组，累加项目时间，若超过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(){ cin>>n>>m; for(int i = 1;i <= n;i++){ cin>>a[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; } } cout<<r; return 0; }

该方法高效且易于实现，适用于大规模数据。