聪哥的工资

(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

思路

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 int n,m;

 int v[];

 int l,r,mid;

 bool work(int large)

 {

     int total=; //记录划分次数

     int sum=;  //记录当前划分次的总和

     for (int i=;i<=n;i++)

     {

         if (v[i]>large) { return false; }

         if ((sum+v[i])>large)

         {

             sum=v[i];

             total+=;

             if (total>m) {return false;}

         }

         else { sum+=v[i]; }

     }

     if ((total+)<=m) {return true;} else {return false;}

 }

 int main()

 {

     freopen("money.in","r",stdin);

     freopen("money.out","w",stdout);

     cin>>n>>m;

     for (int i=;i<=n;i++) {cin>>v[i];r+=v[i];}

     l=;

     while ((r-l)>)

     {

         mid=(l+r)>>;

         if (work(mid)==true) {r=mid;} else {l=mid+; }

     }

     if (work(l)==true) {cout<<l<<endl;} else {cout<<r<<endl;}

     return ;

 }

思路：二分

巴特西

17.2.10 NOIP模拟赛聪哥的工资

题目描述

输入

输出

样例输入

样例输出

样例说明

数据范围

思路

最新文章

热门文章

巴特西

17.2.10 NOIP模拟赛 聪哥的工资

题目描述

输入

输出

样例输入

样例输出

样例说明

数据范围

思路

最新文章

热门文章

17.2.10 NOIP模拟赛聪哥的工资