首页 > 代码库 > 【二分】【中等难度】noip模拟赛 聪哥的工资

【二分】【中等难度】noip模拟赛 聪哥的工资

聪哥的工资

(money/money.in/money.out)

时限1000ms 内存256MB

题目描述

lwher: 了体验劳苦大众的生活,聪哥在暑假参加了打零工的活动,这个活动分为n个工作日,每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间,也就是说什么时候拿钱,老板说的不算,聪哥才有发言权!

(因为聪哥是土豪,他是老板的老板,你觉得老板敢给聪哥安排任务吗?所以聪哥的工作就是看心情去拿钱拿完就走人啦。。。)

聪哥不喜欢身上一次性有太多的钱,于是他想安排一下拿钱的时间,使他一次性拿的钱中最大的最小。(最后一天一定要领钱)

聪哥:晕,就是给你一个数列,让你分成m段,使各段中数字的和最大的最小

输入

第一行 2个数 n,m

接下来n行,每行一个数,代表Vi.

输出

最小的最大钱数。

样例输入

7 5

100

400

300

100

500

101

400

样例输出

500

样例说明 

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

“//”表示聪哥要去拿钱。

数据范围

20%   1<=n<=20

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

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

思路

题面经过我加工一定更霸气了。。。

很明显的二分,看到最大的最小 或者 最小的最大 就是明显二分答案啊。。(这好像是吴桐当年跟我说的——)

二分答案,然后线性扫一遍判断这个答案是否符合就可以了。。。第一次写二分也没觉得太难啊

代码

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 int n,m; 6 int v[100005]; 7 int l,r,mid; 8 bool work(int large) 9 {10     int total=0; //记录划分次数 11     int sum=0;  //记录当前划分次的总和  12     for (int i=1;i<=n;i++)13     {14         if (v[i]>large) { return false; }15         if ((sum+v[i])>large) 16         {17             sum=v[i];18             total+=1;19             if (total>m) {return false;}20         } 21         else { sum+=v[i]; }    22     }23     if ((total+1)<=m) {return true;} else {return false;}24 }25 26 int main()27 {28     freopen("money.in","r",stdin);29     freopen("money.out","w",stdout);30     cin>>n>>m;31     for (int i=1;i<=n;i++) {cin>>v[i];r+=v[i];}32     l=0;33     while ((r-l)>1) 34     {35         mid=(l+r)>>1;36         if (work(mid)==true) {r=mid;} else {l=mid+1; }37     }38     if (work(l)==true) {cout<<l<<endl;} else {cout<<r<<endl;}39     return 0;40 }

 

特意显示了一下行号,40行打完代码你怕不怕?(/偷笑)

结果

时间用了好久啊,。。不过好像也没法优化。。。

 

【二分】【中等难度】noip模拟赛 聪哥的工资