工资
【试题描述】
聪哥在暑假参加了打零工的活动,这个活动分为n个工作日,每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以*安排这些时间,也就是说什么时候拿钱,老板说的不算,聪哥才有发言权!(因为聪哥是土豪,他是老板的老板)
聪哥不喜欢身上一次性有太多的钱,于是他想安排一下拿钱的时间,使他一次性拿的钱中最大的最小。(最后一天一定要领钱)
【输入要求】
最小的最大钱数。
【输出要求】
最小的最大钱数。
【输入实例】
7 5
100
400
300
100
500
101
400
【输出实例】
500
【其他说明】
数据范围:
20% 1<=n<=20
另 20% 1<=n<=50,Vi的和不超过1000
100% 1<=n<=100,000,m<=n,Vi<=10,000
【试题分析】
非常明显的二分题,这题貌似是我AK那天yy的第二题,第一眼没头绪,再想一想就简单多了,先把二分写出来,想明白right的值和left的值,要想明白,这里不是按个数二分的,而是按钱数二分的,由于right和left没想好,所以调了30多分钟程序QAQ,具体过程我们还是来直接看代码吧!
【代码】
#include<iostream>
using namespace std;
inline long long read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int n,m;
long long v[101000];
long long l=-9999999,r;//为了后面要做好准备,不然……
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
v[i]=read();
if(l<v[i]) l=v[i];//一开始l写对了,r写成v最大的数字了QAQ
r+=v[i];
}
while(l<r)
{
long long mid=(l+r)/2;
long long sum=0;
long long time=1;
for(int i=0;i<n;i++)
{
sum+=v[i];//sum+v[i]记录这一块的工资值
if(sum>mid)
{
time++;
sum=v[i];//重新开始
}
}
if(time<=m) r=mid;//二分
else l=mid+1;
}
printf("%lld",l);//由于l和r的值一样,所以可以输出任何一个
}