【二分】LOJ 1048 Conquering Keokradong

KIDx 的解题报告

 

题目链接：http://lightoj.com/volume_showproblem.php?problem=1048

 

题意：给n+1个数，要你通过合并使其变成k+1个数，要求令这k+1个数的最大值最小，另外输出时尽量让前面的大

#include <iostream>
using namespace std;
#define M 1005

int n, a[M], k;

bool judge (int key)			//暴力检验
{
	int i = 0, num = 0;
	while (i < n)
	{
		int tp = a[i++];
		if (tp > key)			//以key为最大值，因此需检验每个元素是否<=key
			return false;
		for ( ; i < n; i++)
		{
			if (tp + a[i] <= key)
			{
				tp += a[i];
				num++;
			}
			else break;
		}
	}
	if (num >= n - k)			//合并次数要符合，不可放到上面的for循环里
		return true;			 //因为还要满足每个元素都<=key
	return false;
}

int main ()
{
	int t, cc = 1, l, r, mid, i, num;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%d", &n, &k);
		n++, k++;
		l = r = 0;
		for (i = 0; i < n; i++)
		{
			scanf ("%d", a+i);
			r += a[i];
		}
		while (l < r)		//二分枚举最大值
		{
			mid = (l+r) >> 1;
			if (judge (mid))
				r = mid;
			else l = mid + 1;
		}
		printf ("Case %d: %d\n", cc++, r);
		i = num = 0;
		/***********按题意尽量让前面的大***********/
		while (i < n)
		{
			int tp = a[i++];
			if (num < n - k) for ( ; i < n; i++)
			{
				if (tp + a[i] <= r)
				{
					tp += a[i], num++;
					if (num == n - k)	//合并n-k次就不能再合了！
					{
						i++; break;
					}
				}
				else break;
			}
			printf ("%d\n", tp);
		}
		/***********按题意尽量让前面的大***********/
	}
	return 0;
}