友善题解 #2 复制书稿

2020 年 08 月 04 日

357 次浏览

718字数

[题目链接](https://www.luogu.com.cn/problem/P1281)

首先，通关观察题意，发现是让我们选择分类。

那么我们一开始需要得到**最少的时间**这个变量。所以我们可以二分答案查找这个最少的时间。找到这个最少的时间之后再去枚举这个过程。当然这道题中，尽量让前面的人少抄写。也就是让后面的人多抄写，那就从后往前，尽可能的多拿，剩下的就是前面需要拿的。

Code:

```cpp
// Problem: 书的复制

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 501;

int a[MAXN + 1];

int n, m;

bool check(int x)
{
	int cnt = 0, k = 1;
	for (int i = 1; i <= n; i ++ )
	{
		if (a[i] > x)
		{
			return false;
		}
		if (cnt + a[i] > x)
		{
			k ++;
			cnt = a[i];
		}
		else
		{
			cnt += a[i];
		}
	}
	return k <= m;
}

pair<int, int> res[10001];

void getans(int x)
{
	int k = m, f = 0;
	res[k].first = n;
	for (int i = n; i >= 1; i -- )
	{
		f += a[i];
		if (f > x)
		{
			f = a[i];
			res[k].second = i + 1;
			k --;
			res[k].first = i;
		}
	}
	res[1].second = 1;
	for (int i = 1; i <= m; i ++ )
	{
		printf("%d %d\n", res[i].second, res[i].first);
	}
}

int main()
{
	int l, r;
	scanf("%d%d", &n, &m);
	l = 1;
	r = 100001;
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
	}
	while(r - l > 5)
	{
		int mid = (r + l) / 2;
		if (check(mid))
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}
	int res = 0;
	for (int i = l; i <= r; i ++ )
	{
		if (check(i))
		{
			res = i;
			break;
		}
	}
	getans(res);
	return 0;
}
```

最后立个Flag, 这几天写一下二分答案的博客。

* [ ] 是否填坑

最后修改：2020 年 08 月 10 日