Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- using namespace std;
- int getParts(long long int arr[501],int n,long long int mid,int k);
- int slash[501];
- int ind=0;
- int main(){
- int t,n,k,i,p;
- long long int arr[501],mid,sum,max,lo,hi,group;
- scanf("%d",&t);
- while(t--){
- scanf("%d%d",&n,&k);
- long sum=0,max=-1;
- for(i=0;i<n;i++){
- scanf("%llu",&arr[i]);
- sum+=arr[i];
- if(max<arr[i]){
- max=arr[i];
- }
- }
- lo=max,hi=sum;
- while(lo<hi){
- mid=(hi+lo)/2;
- // printf("%d \n",mid);
- group=getParts(arr,n,mid,k)+1;
- // printf("%llu\n",parts+1);
- if(group<=k){
- hi=mid;
- }
- else{
- lo=mid;
- }
- // printf("lo=%d, hi=%d, mid=%d ,group=%d\n",lo,hi,mid,group);
- if(lo+1==hi){
- break;
- }
- }
- // for(i=0;i<k-1;i++){
- // printf("-%d ",slash[i]);
- // }
- p=k-2;
- for(i=0;i<n;i++){
- printf("%llu ",arr[i]);
- if(p>=0){
- //printf("slash[p]=%d i+1=%d\n",slash[p],i+1);
- if(i+1==slash[p]){
- printf("/ ");
- p--;
- }
- }
- }
- // sort(slash);
- printf("\n");
- }
- return 0;
- }
- int getParts(long long int arr[501],int n,long long int mid,int k){
- long long int sum=0,i;
- int parts=0;
- ind=0;
- for(i=n-1;i>=0;i--){
- sum+=arr[i];
- if(sum>mid){
- if(ind<k-1){
- slash[ind]=i+1;
- ind++;}
- parts++;
- sum=arr[i];
- }
- //if(parts)
- }
- return parts;
- }
- /*2
- 9 3
- 1 2 3 4 5 6 7 8 9*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement