【NYNU 1148】妹妹的工资怎么算 二分

原题地址：http://47.93.252.151/problem.php?id=1148

                                       1148: 妹妹的工资怎么算

题目描述

《我的妹妹哪有这么可爱！》中的女主叫做高坂桐乃，高坂家的幺女，外表出众、成绩优秀、运动万能的少女，而且还兼职流行杂志的专属模特。阳光的外表下却有着特别的兴趣，是个在意周围眼光的御宅族，喜欢妹系的***和动梅露露的动画。桐乃有很多的工作，这次她有接到一个模特工作，这次一共工作n天，每天的工资为vi 有m个结算工资的日子，因为桐乃还是初中生所以她可以任意挑选m天来拿工资，但是桐乃每次不想拿太多的钱，所以她想计划使她一次性拿的钱中的最大的最小，（最后一天一定要拿工资）但是她不会分配日子，按照惯例，她找来了哥哥京介进行“人生咨询”，想让哥哥帮忙解决这个问题，哥哥也不怎么会，但是哥哥怎么会拒接妹妹的请求呢，所以他来拜托你解决这个问题。

输入

第一行 两个数 n ,m（m<=n<=100000）

第二行 n个数，vi   (vi<100000)

输出

一个数表示答案

样例输入

5 3
1 2 3 4 5

样例输出

6

提示

解释：1 2 3// 4// 5 //  //为拿工资

在每次结算时拿到尽量少的工资的前提下，求出拿到的最多工资是多少。

显然，存在一个值，使得n天的工资分成m份，每份工资恰好都大于该值，二分找出即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

ll a[100005];

int main()
{
	ll n,m,i,l=0,r=0;        //1w*1w 会爆int
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		r+=a[i];
		l=max(l,a[i]);
	}
	while(l<=r)
	{
		ll mid=(l+r)/2;
		ll s=0,ans=1;
		for(i=0;i<n;i++)
		{
			if(s+a[i]>mid)
			{
				s=0;
				ans++;
			}
			s+=a[i];
		}
		if(ans>m)
			l=mid+1;
		else
			r=mid-1; 
	}
	cout<<l<<endl;
	return 0;	
}