LIGHTOJ1048_Conquering Keokradong

这个题也是一开始的思路不对。链接：戳我刷题

题意：给定n+1个数，分成k+1个组，每个组中的数需要是连续的

要求各组数求和的最大值最小。

两个最值的理解，求最大是说，在某一种分组情况中，k+1个组中，每个组求和后的k+1个数取最大

求最小是说，在所有的k+1个组的方法分配中，各个最大数比较的最小的方案

由于n和k都比较小，n最大1000，k最大300，一看就是典型的dp【i】【j】的结构，数组也可以开，想得特别完美

dp【i】【j】定义为：前n个数，分成k组的最大数的最小值是多少

dp【n+1】【k+1】为最终答案

dp是状态定义，答案定义，边界值dp【0】【0】，可以状态转移太不好写

于是想到了另一种方法：二分求最值

其实我只需要判断x可以作为该值，而x-1不行，那么x肯定是最终答案

所以，定义二分，代入值判断而不是求值是更好的方法

// lightoj 1048 - Conquering Keokradong 二分答案

#include<bits/stdc++.h>
using namespace std;

int n,k,a[1050];

int judge(int x){
	//判断x值能不能作为答案所需要的那个值 
	int cnt=0,tmp=0;
	for(int i=1;i<=n;i++){
		//存在任意一个大于x的值
		//该分配方案肯定不合法 
		if (a[i]>x) return 0;
		if (tmp+a[i]<=x)  tmp+=a[i];
		else{
			tmp=a[i];
			cnt++;
		}
	}
	return cnt<=k;
	//等于k可以
	//小于k是更可以的，无非就是把大数拆分成小数啊 
}

int main(){
	//freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d",&n,&k);
		n++;
		int l=0,r=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			r+=a[i];
			l=max(l,a[i]);
		}
		int ans,mid;
		while(l<=r){
			mid=(l+r)>>1;
			if (judge(mid)){
				r=mid-1;
				ans=mid;
			}
			else l=mid+1;
		}
		printf("Case %d: %d\n",Case,ans);
		int tmp=0,cnt=0;
		for(int i=1;i<=n;i++){
			if (tmp+a[i]>ans||n-i<k-cnt){
				//边界：
				//到了不得不每一个数分一组的情况了 
				printf("%d\n",tmp);
				tmp=a[i];
				cnt++;
			}
			else tmp+=a[i];
		}
		printf("%d\n",tmp);
	}
	return 0;
}