更新时间:2022-08-12 16:35:29
思路:二分
分析:
1 题目给定n天的消费金额,已经要分成的m部分。现在问我们在所有可分的情况下,最大一部分的和的最小值。
2 如果m =1 ,那么最大的一部分就是sum;如果m = n,那么最大的一部分就是n个数的人最大值max;根据1=<m<=n可以知道这个ans肯定是在[max,sum]之间,那么我们就可以利用二分的思想,去二分这个ans,然后找到最小的并且满足条件的;
3 由于题目明确指出每一部分的天数是连续的,那么我们在判断是否满足的时候就只要枚举一些即可。
4 注意一下二分的上下界,二分的上下界是有严格要求的。
代码:
#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 100010 int n , m , sum , Min; int money[MAXN]; void solve(){ int left , right , mid; left = Min , right = sum; while(left < right){ mid = left+(right-left)/2;/*这里为了不溢出采用这个方法*/ int tmpSum = 0; int count = 1;/*至少有一个组*/ for(int i = 0 ; i < n ; i++){ tmpSum += money[i]; if(tmpSum > mid){ tmpSum = money[i]; count++; } } if(count <= m)/*如果分的组刚好小于等于m说明mid值大了*/ right = mid; else left = mid+1; } printf("%d\n" , left); } int main(){ while(scanf("%d%d" , &n , &m) != EOF){ Min = 0 , sum = 0; for(int i = 0 ; i < n ; i++){ scanf("%d" , &money[i]); sum += money[i]; Min = max(Min , money[i]); } solve(); } return 0; }