月度开销
描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M，用单个空格隔开。
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。
输出
一个整数，即最大月度开销的最小值。
样例输入
1
2
3
4
5
6
7
8
| 7 5
100
400
300
100
500
101
400
|
样例输出
提示
若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <cstdio>
using namespace std;
int num[100000];
int m, n;
long long solve(long long left, long long right){
if(left == right){
return left;
}
else{
long long mid = (left + right) / 2;
int month = 0;
long long cost = 0;
for(int i = 0; i < n; i++){
if(cost + (long long)num[i] <= mid){
cost += (long long)num[i];
}
else if((long long)num[i] <= mid){
month += 1;
cost = (long long)num[i];
if(month > m){
break;
}
}
else{
break;
}
}
if(month < m){
return solve(left, mid);
}
else{
return solve(mid + 1, right);
}
}
}
int main(void){
long long left = 0;
long long right = 0;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
if(left < num[i]){
left = (long long)num[i];
}
right += (long long)num[i];
}
printf("%lld", solve(left, right));
return 0;
}
|
