欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA-714抄书

程序员文章站 2022-06-03 14:21:02
...

UVA-714抄书
因为子序列的和一定不大于整个序列的和,先求出整个序列的和 和 其中最大的一个,作为R和L,然后进行二分。找到使得子序列和最小的那个数。
然后在这个基础上,看能不能优化划分方式,使得前面的划分序列和尽量小。
PS:求序列和用long long

#include <cstdio>
#include <cstring>
const int N = 500+5;
int A[N]; 
int ans[N];

int main()
{
	//freopen("in.txt","r",stdin);
	int T,n,k; scanf("%d",&T);
	while( T-- ){
		scanf("%d %d",&n,&k);
		long long sum = 0;
		int maxd = -1;
		for(int i = 1; i <= n; ++i) {
			scanf("%d",&A[i]);
			if( A[i]>maxd ) maxd = A[i];
			sum+= A[i];
		}
		if(k == 1) { for(int i = 1; i < n; ++i) printf("%d ",A[i]); printf("%d\n",A[n]); continue;}
	
		long long L = maxd, R = sum;
		
		while(L < R){
			long long m = (L+R)/2;
			long long cur_sum = 0;
			int cnt = 1;
			for(int i = 1; i <= n; ++i){
				if(cur_sum + A[i] <= m) cur_sum+= A[i];
				else { cur_sum = A[i]; ++cnt; }
			}
			if(cnt <= k)  R = m;// m可以作为最大值 
			else L = m+1;
		}
		//printf("max is %d\n",L);
		//看能不能再最大和为m的前提下,让前面的序列和尽量小 ,更新答案 
		memset(ans,0,sizeof(ans));
		int remain = k;
		long long cur_sum = 0;
		for(int i = n; i >= 1; --i){
			if(cur_sum + A[i] > L||i < remain) { ans[i] = 1; --remain; cur_sum = A[i]; }
			else cur_sum += A[i];
		}
	
		for(int i = 1; i < n; ++i) {
			printf("%d ",A[i]);
			if(ans[i]) printf("/ "); 
		}
		printf("%d\n",A[n]);
	}
	//fclose(stdin);
	return 0;
}