Description

小X同學(xué)給小C同學(xué)選了N件禮物，決定順序購(gòu)買(mǎi)并贈(zèng)送，但作為一個(gè)沒(méi)有工資沒(méi)有零花錢(qián)的可憐小朋友，有M位好心的同學(xué)伸出了援助之手，然而為了減少最高的借款量，小X同學(xué)希望OI競(jìng)賽的你為他合理規(guī)劃，使得他能輕松快樂(lè)地送出禮物。

Input

第一行輸入兩個(gè)用空格隔開(kāi)的正整數(shù)N和M
以下N行每行一個(gè)不超過(guò)10000正整數(shù)，依次表示禮物的價(jià)格。

Output

一個(gè)整數(shù)，即最高借款量。

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

Hint

數(shù)據(jù)范圍：
30%：n <=10
60%: n<=1000
100%: n<=100000

程序：

var a:array[0..200000]of longint;n,m,i,l,r,mid,t,s:longint; beginreadln(n,m); l:=0;for i:=1 to n dobeginreadln(a[i]);if a[i]>l then l:=a[i];end;l:=l-1; r:=maxlongint div 2;while l+1<r dobeginmid:=(l+r) div 2;t:=0; s:=0;for i:=1 to n dobeginif s+a[i]>mid then begin inc(t); s:=0; end;s:=s+a[i];end;if t>m then l:=mid else r:=mid;end;writeln(r); end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500048.html

總結(jié)

以上是生活随笔為你收集整理的2017年9月9日普级组 买礼物的艰辛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。