记录编号	314908	评测结果	AAAAAAAAAA
题目名称	书的复制	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-10-04 14:11:24	内存使用	0.32 MiB

#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;

int m, k, book[110];
int sum[110], s[110], t[110];

inline bool Check(const int& mid)
{
	memset(s, 0, sizeof(s));
	memset(t, 0, sizeof(t));
	int pos = m + 1;
	for(int i = k; i; i--){
		int j = pos - 1;
		if (sum[pos-1]-sum[j-1] > mid){
//			puts("judge");
			return 0;
		}
		for(j = pos - 1; j && sum[pos-1]-sum[j-1] <= mid; j--);
		s[i] = ++j; t[i] = pos - 1; pos = j;
//		printf("s[%d]:%d t[%d]:%d\n", i, s[i], i, t[i]);
		if(s[i] == 1 && i != 1) return 1;
	}
	if(s[1] != 1) return 0;
	return 1;
}

int main()
{
	freopen("books.in", "r", stdin); freopen("books.out", "w", stdout);
	scanf("%d%d", &m, &k);
	for(int i = 1; i <= m; i++){
		scanf("%d", &book[i]);
		sum[i] = sum[i-1] + book[i];
	}
	int l = 0, r = sum[m], mid;
	while(l <= r){
		mid = (l + r) >> 1;
//		printf("l:%d r:%d mid:%d\n", l, r, mid);
		if(Check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	if(Check(l)){
//		printf("ans:%d\n", l); 
		for(int i = 1; i <= k; i++) printf("%d %d\n", s[i], t[i]);
	}
	else if(Check(r)){
//		printf("ans:%d\n", r); 
		for(int i = 1; i <= k; i++) printf("%d %d\n", s[i], t[i]);
	}

	return 0;
}
/*
book.in
9 3
1 2 3 4 5 6 7 8 9

book.out
1 5
6 7
8 9

*/
/*
10 6
11 3 2 5 10 11 11 5 5 6 

ans: 16
*/