首页 > 代码库 > 【二分】【中等难度】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模拟赛 聪哥的工资
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。