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