You are given n packages of wi kg from a belt conveyor in order (i=0,1,…n?1). You should load all packages onto k trucks which have the common maximum load P. Each truck can load consecutive packages (more than or equals to zero) from the belt conveyor unless the total weights of the packages in the sequence does not exceed the maximum load P.

Write a program which reads n, k and wi, and reports the minimum value of the maximum load P to load all packages from the belt conveyor.

Input

In the first line, two integers n and k are given separated by a space character. In the following n lines, wi are given respectively.

Output

Print the minimum value of P in a line.

Constraints

1≤n≤100,000
1≤k≤100,000
1≤wi≤10,000

Sample Input 1

5 3
8
1
7
3
9

Sample Output 1

10
If the first truck loads two packages of {8,1}, the second truck loads two packages of {7,3} and the third truck loads a package of {9}, then the minimum value of the maximum load P shall be 10.

Sample Input 2

4 2
1
2
2
6

Sample Output 2

6
If the first truck loads three packages of {1,2,2} and the second truck loads a package of {6}, then the minimum value of the maximum load P shall be 6.

思路

確定最大運載量P時，首先要編寫一個算法來計算k輛以內的卡車總共能裝多少貨物。

思路很簡單，只要卡車的運載量沒達到P，就讓其繼續按順序裝貨物，最后再計算所有卡車運載量的總和即可。

以P為實參，編寫一個返回可裝載貨物數v的函數v=f§，這個函數的算法復雜度為O(n)。

現在只需要調用這個函數，讓P從0開始逐漸自增，第一個讓v大于等于n的P就是答案。但是逐個檢查P會失敗的原因算法復雜度達到O(Pn)，程序不可能在限制時間內完成處理。

利用“P增加v不會減少”的性質，用二分搜索來求P，算法復雜度降低至O(n*log P)。

code

/*^....0^ .1 ^1^.. 011.^ 1.0^ 1 ^ ^0.11 ^ ^..^0. ^ 0^.0 1 .^.1 ^0 .........001^.1 1. .111100....01^00 ^ 11^ ^1. .1^1.^ ^0 0^.^ ^0..1.1 1..^1 .0 ^ ^00. ^^0.^^ 0 ^^110.^0 0 ^ ^^^10.01^^ 10 1 1 ^^^1110.101 10 1.1 ^^^1111110010 01 ^^ ^^^1111^1.^ ^^^10 10^ 0^ 1 ^^111^^^0.1^ 1....^11 0 ^^11^^^ 0.. ....1^ ^ ^1. 0^ ^11^^^ ^ 1 111^ ^ 0.10 00 11 ^^^^^ 1 0 1.0^ ^0 ^0 ^^^^ 0 0.0^ 1.0 .^ ^^^^ 1 1 .0^.^ ^^ 0^ ^1 ^^^^ 0. ^.11 ^ 11 1. ^^^ ^ ^ ..^^..^ ^1 ^.^ ^^^ .0 ^.00..^ ^0 01 ^^^ .. 0..^1 .. .1 ^.^ ^^^ 1 ^ ^0001^ 1. 00 0. ^^^ ^.0 ^.1. 0^. ^.^ ^.^ ^^^ ..0.01 .^^. .^ 1001 ^^ ^^^ . 1^. ^ ^. 11 0. 1 ^ ^^ 0.0 ^. 0 ^0 1 ^^^ 0.0.^ 1. 0^ 0 .1 ^^^ ...1 1. 00 . .1 ^^^ ..1 1. ^. 0 .^ ^^ ..0. 1. .^ . 0 ..1 1. 01 . . ^ 0^.^ 00 ^0 1. ^ 1 1.0 00 . ^^^^^^ ..^ 00 01 ..1. 00 10 1 ^^.1 00 ^. ^^^ .1.. 00 .1 1..01 ..1.1 00 1. ..^ 10^ 1^ 00 ^.1 0 1 1.1 00 00 ^ 1 ^. 00 ^.^ 10^ ^^1.1 00 00 10^..^ 1. ^. 1.0 1 ^. 00 00 .^^ ^. ^ 1 00 ^0000^ ^ 011 0 ^. 00.0^ ^00000 1.00.1 11. 1 0 1^^0.01 ^^^ 01.^ ^ 1 1^^ ^.^1 1 0... 1 ^1 1^ ^ .01 ^ 1.. 1.1 ^0.0^ 0 1..01^^100000..0^1 1 ^ 1 ^^1111^ ^^0 ^ ^ 1 1000^.1 ^.^ . 00.. 1.1 0. 01. . 1. .^1. 1 1. ^0^ . ^.1 00 01^.0 001. .^*/ // Virtual_Judge —— Allocation Aizu - ALDS1_4_D.cpp created by VB_KoKing on 2019-05-04:11. /* Procedural objectives：Variables required by the program:Procedural thinking：Functions required by the program:*/ /* My dear Max said： "I like you, So the first bunch of sunshine I saw in the morning is you, The first gentle breeze that passed through my ear is you, The first star I see is also you. The world I see is all your shadow."FIGHTING FOR OUR FUTURE！！！ */ #include <iostream> #define MAX 100007 using namespace std;int n,k; long long T[MAX];//k輛最大運載量為p的卡車能裝多少貨物 int check(long long p) {int i=0;for (int j = 0; j < k; j++) {long long s=0;while (s+T[i]<p+1){s+=T[i];i++;if (i==n)return n;}}return i; }int solve() {long long left=0;long long right=100000*10000; //貨物數*1件貨物的最大重量long long mid;while (right-left>1){mid=(right+left)/2;int v=check(mid);if (v>n-1) right=mid;else left=mid;}return right; }int main() {cin>>n>>k;for (int i = 0; i < n; i++)cin>>T[i];long long ans=solve();cout<<ans<<endl;return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Allocation Aizu - ALDS1_4_D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。