记录编号	202599	评测结果	AAAAAAAAAA
题目名称	书的复制	最终得分	100
用户昵称	qzyz_czs	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-11-01 16:01:45	内存使用	0.32 MiB

#include <fstream>
#include <algorithm>


using namespace std;


const int MaxN = 1000 + 10;


int a[MaxN], n, k, ans[MaxN];


void binary(int , int );
bool check(int );


int main(void)
{
	ifstream cin("books.in");
	cin >> n >> k;
	int lowerlimit = 0, upperlimit = 0;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		lowerlimit = max(lowerlimit, a[i]);
		upperlimit += a[i];
	}
	cin.close();
	
	binary(lowerlimit, upperlimit + 1);
	ans[0] = 1;
	ans[k] = n + 1;
	
	ofstream cout("books.out");
	for (int i = 1; i <= k; ++i)
		cout << ans[i - 1] << ' ' << ans[i] - 1 << endl;
	cout.close();
	
	return 0;
}


void binary(int l, int r)
{
	if (l == r - 1)
	{
		check(l);
		return ;
	}
	int mid = (l + r) / 2;
	if (check(mid - 1))
		binary(l, mid);
	else
		binary(mid, r);
}


bool check(int val)
{
	for (int i = 1, sum = 0, tot = 0; i <= n; ++i)
		if ((sum += a[i]) > val)
		{
			ans[++tot] = i;
			if (tot >= k)
				return 0;
			sum = a[i];
		}
	return 1;
}