【二分】LOJ 1048 Conquering Keokradong _C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【二分】LOJ 1048 Conquering Keokradong

【二分】LOJ 1048 Conquering Keokradong

 2012/1/17 9:08:23  基德KID.1412  程序员俱乐部  我要评论(0)
  • 摘要:KIDx的解题报告题目链接:http://lightoj.com/volume_showproblem.php?problem=1048题意:给n+1个数,要你通过合并使其变成k+1个数,要求令这k+1个数的最大值最小,另外输出时尽量让前面的大#include<iostream>usingnamespacestd;#defineM1005intn,a[M],k;booljudge(intkey)//暴力检验{inti=0,num=0;while(i<n)
  • 标签:RAD

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;
}

?

发表评论
用户名: 匿名