【題目描述】：

聰哥在暑假參加了打零工的活動(dòng)，這個(gè)活動(dòng)分為n個(gè)工作日，每個(gè)工作日的工資為Vi。有m個(gè)結(jié)算工錢的時(shí)間,聰哥可以自由安排這些時(shí)間，也就是說什么時(shí)候拿錢，老板說的不算，聰哥才有發(fā)言權(quán)！（因?yàn)槁敻缡峭梁?#xff0c;他是老板的老板）

聰哥不喜歡身上一次性有太多的錢，于是他想安排一下拿錢的時(shí)間，使他一次性拿的錢中最大的最小。（最后一天一定要領(lǐng)錢）

【輸入描述】：

第一行 2個(gè)數(shù) n,m

接下來n行，每行一個(gè)數(shù)，代表Vi。

【輸出描述】：

最小的最大錢數(shù)。

【樣例輸入】：

7 5 100 400 300 100 500 101 400

【樣例輸出】：

500

【樣例說明】：

100 400//300 100//500//101//400//

“//”表示老大要去拿錢。

【時(shí)間限制、數(shù)據(jù)范圍及描述】：

時(shí)間：1s 空間：256M

20% ： 1<=n<=20

另20%：1<=n<=50, Vi的和不超過1000

100%： 1<=n<=100,000, m<=n, Vi<=10,000

1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=100005; 5 int n,m; 6 LL a[MAX]; 7 LL low,high,mid; 8 void init(){ 9 int i,j; 10 scanf("%d%d",&n,&m); 11 for (i=1;i<=n;i++){ 12 scanf("%lld",a+i); 13 low=max(low,a[i]); 14 high+=a[i]; 15 } 16 } 17 bool feasible(LL x){ 18 int i,j; 19 LL zt=0,an=0; 20 for (i=1;i<=n;i++){ 21 if (a[i]+zt>x){ 22 zt=a[i]; 23 an++; 24 } 25 else 26 zt+=a[i]; 27 } 28 return (an>=m); 29 } 30 int main(){ 31 init();int i,j; 32 while (low<=high){ 33 mid=(low+high)>>1; 34 if (feasible(mid)) 35 low=mid+1; 36 else 37 high=mid-1; 38 } 39 printf("%d",low); 40 return 0; 41 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/keximeiruguo/p/7309771.html

總結(jié)

以上是生活随笔為你收集整理的WHYZOJ-#60 工资(二分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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