计算思维训练-期末考

前言：暑假吼吼吼放完假就可以开学了吼吼吼

Problem D. 分米粒

时间限制 ？？ ms
内存限制 ？？ MB

题目描述
//因为过时间看不到了所以不可描述
大概意思是有n堆按顺序的米，你可以拿隔板把它们隔开，两隔板之间的若干堆米为一份。已知你有m块隔板。求经过你睿智的隔板设置后，每份米的最大值，最小是多少。

输入数据
//不可描述

输出数据
//不可描述

样例输入
//不记得样例了，再来一个

5 2
7 2 1 9 3
12
5 3
3 9 1 2 7
10

样例输出
12
10

样例说明
无

---

算法

二分查找模板题。
不过有些同学考试的时候比较紧张，可能没有看出来。因为这道题没有排序嘛，会觉得噫这题不用排序那是不是就不能用二分查找了？其实不然。
我们看看这道题满足什么条件？米堆的顺序不可调整！也就是有一个数组a[i]，它的顺序是不变的。如果二分查找的题目做多了，就很发现它其实是很常见的一种应用二分查找的题型。

二分查找是在，前面的如果能满足，后面的一定能满足，的条件下才能使用。再来看这道题，如果 每份米的最大值 最小不超过10，那 每份米的最大值 最小是不是肯定不超过比10大的数？是的，那么它就可以使用二分查找。

接下来说说怎么用，也就是二分查找的Check()函数怎么写。
我们在放隔板的时候，因为米堆的顺序固定，所以一旦某一堆的和+a[i]超过了k，我们就得在a[i]之前放一个隔板。也就是说，我们可以在循环1-n时，每次累加当前米堆的和，当它要超过k时，隔板数+1。如果某时刻隔板数>m，你就知道，米堆最大值最小是k这个条件，是无法满足的，return false。

---

下面是具体的代码实现。

bool Check(int x)
{
	int sum=0,cnt=0;
	ufor (i,1,n)
	{
		if (sum+a[i]>x) sum=a[i],cnt++; else sum+=a[i];
	}
	return cnt+1<=m;
}

int main()
{

	while (scanf("%d%d",&n,&m)!=EOF)
	{
		int summ=0,maxx=0;
		ufor (i,1,n)
		{
			scanf("%d",&a[i]);
			summ+=a[i];
			maxx=max(maxx,a[i]);
		}
		int l=maxx,r=summ;
		while (l<r)
		{
			int mid=(l+r)/2;
			if (Check(mid)) r=mid; else l=mid+1;
		}
		//printf("%d\n",r);
		//while (!Check(r)) r--;
		cout<<l<<endl;
	}

	return 0;
}

打赏