WA代码求调
查看原帖
WA代码求调
672237
qinshi0308楼主2023/5/22 22:09

rt

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[510];
inline bool check(ll x,int m,int k){
//	cout<<x<<endl;
	ll sum=arr[0];
	int ans=1;
	for(int i=1;i<m;i++){
		if(sum+arr[i]<=x){
			sum+=arr[i];
		}else{
			sum=arr[i];
			ans++;
		} 
	}
	return ans<=k?1:0;
}
inline ll work(ll l,ll r,int m,int k){
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid,m,k)){
			r=mid-1;
		}else{
			l=mid+1;
		}
//		cout<<l<<" "<<r<<" "<<mid<<" "<<check(mid,m,k)<<endl;
	}
	return l;
}
inline void print(ll ans,int m,int k){
	stack<int> s;
	ll sum=0;
	k--;
	for(int i=m-1;i>=0;i--){
		if(k==i+1){
			while(i>=0){
				s.push(-1);
				s.push(arr[i]);
				i--;
			}
			continue;
		}
		if(sum+arr[i]<=ans){
			sum+=arr[i];
			s.push(arr[i]); 
//			cout<<arr[i]<<" ";
		}else{
			sum=arr[i];
			s.push(-1);
			s.push(arr[i]);
			k--;
//			cout<<arr[i]<<" / ";
		} 
	}
	while(s.size()){
		if(s.top()==-1){
			cout<<"/ ";
			s.pop();
		}else{
			cout<<s.top()<<" ";
			s.pop();
		}
	}
}
int main(){
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		int m,k;
		cin>>m>>k;
		ll l=0;
		ll r=0;
		for(int j=0;j<m;j++){
			cin>>arr[j];
			l=max(l,arr[j]);
			r+=arr[j];
		}
		int ans=work(l,r,m,k);
		cout<<ans<<endl;
		print(ans,m,k);
		cout<<endl;
	}
	return 0;
}
2023/5/22 22:09
加载中...