紫书例题8-10 UVa 714 （二分答案）

这道题让最大值最小，显然是二分答案

当题目求的是最大值最小，最小值最大，这个时候就要想到二分答案

为什么可以二分答案呢，因为这个时候解是单调性的，如果简单粗暴一点

就全部枚举一遍，验证答案。但是因为答案满足单调性，可以用二分的方法

来”枚举“，复杂度可以从n降到logn

开始我自己写了一个，但是WA, 后来看了刘汝佳的代码，发现要注意三点

（1）这道题的和的最大值会爆int，要用long long。

养成看到题目的时候计算最大值看会不会爆int的习惯（int最大大概是2乘10的9次方）

（2）输出的时候，因为是前面的子序列的和尽量小，所以我自己写的时候想到了从后

往前尽量取（贪心）来输出，但是没有考虑到分成固定要分成k个。所以要专门用一个remain

来控制分成子序列的个数，不然子序列会分少。

（3）二分开始时候的左端点一定要设为元素最大值，我一开始有想到，但是觉得好像

对答案没有什么影响，就懒得去求最大值，就直接设为0，然后就WA了。

事实上，在判断这个答案是否符合的时候（我的程序中的judge函数），这个key值

根本就小于元素的时候，是可以通过的，这个错误是非常难发现的，所以要提前

处理，也就是在一开始的时候最小的可能的答案就设为元素最大值

顺便提一下，我的程序中l--，是因为我的二分的写法是这么写的。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 512;

int a[MAXN], board[MAXN], n, k;

bool judge(ll key)

{

	ll num = 1, sum = 0;

	REP(i, 0, n)

	{

		if(sum + a[i] <= key) sum += a[i];

		else

		{

			num++; sum = a[i];

			if(num > k) return false;

		}

	}

	return true;

}

void print(ll key)

{

	memset(board, 0, sizeof(board));

	ll sum = 0, remain = k;

	for(int i = n - 1; i >= 0; i--)

	{

		if(sum + a[i] > key || i + 1 < remain)

			sum = a[i], board[i+1] = 1, remain--;

		else sum += a[i];

	}

	printf("%d", a[0]);

	REP(i, 1, n)

	{

		if(board[i]) printf(" /");

		printf(" %d", a[i]);

	}

	puts("");

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		ll l = 0, r = 0;

		scanf("%d%d", &n, &k);

		REP(i, 0, n)

			scanf("%d", &a[i]), r += a[i], l = max(l, (ll)a[i]);

		l--;

		while(l + 1 < r)

		{

			ll mid = (l + r) / 2;

			if(judge(mid)) r = mid;

			else l = mid;

		}

		print(r);

	}

	return 0;

}

巴特西

紫书例题8-10 UVa 714 （二分答案）

最新文章

热门文章

巴特西

紫书 例题8-10 UVa 714 （二分答案）

最新文章

热门文章

紫书例题8-10 UVa 714 （二分答案）