BOOKS1 - Copying Books

很显然看到要求最大值最小就可以想到二分答案，然后依次判断长度是否合法。

这题的输出比较特殊越靠前的区间长度越小，所以我们要将最后得到的答案从后向前依次划分区间即可。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=510; 
int t;
int n,k;
int a[N];

int check(int x){
	ll sum=0;
	int cnt=1;
	for(int i=1;i<=n;i++){
		if(sum+a[i]<=x){
			sum+=a[i];
		}
		else{
			sum=a[i];
			cnt++;
		}
	}
	return cnt<=k;
} 
int p[N];
void print(int x){
	ll sum=0;
	int cnt=k;
	memset(p,0,sizeof p);//标记是否需要划分 
	
	for(int i=n;i>=1;i--){//从后向前划分 
		if(cnt>i){
			p[i]=1;
			cnt--;
		}
		else if(a[i]+sum>x){
			sum=a[i];
			p[i]=1;
			cnt--;
		}
		else{
			sum+=a[i];
		}
	}
	
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
		if(p[i]){
			cout<<"/ ";
		}
	}
	cout<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
    	cin>>n>>k;
		
		ll l=0,r=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			l=max(l,(ll)a[i]);//最小的答案也不能小于最大的a[i] 
			r+=a[i];//最大的答案是长度总和
		}
    	while(l<=r){
    		int mid=(l+r)>>1;
    		if(check(mid)){
    			r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
//    	cout<<l<<"\n";
    	print(l);
	}
    return 0;
}