Advertisement
Guest User

Untitled

a guest
Sep 3rd, 2015
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. #include<cstdio>
  2. using namespace std;
  3. int getParts(long long int arr[501],int n,long long int mid,int k);
  4. int slash[501];
  5. int ind=0;
  6. int main(){
  7. int t,n,k,i,p;
  8. long long int arr[501],mid,sum,max,lo,hi,group;
  9. scanf("%d",&t);
  10. while(t--){
  11.  
  12. scanf("%d%d",&n,&k);
  13. long sum=0,max=-1;
  14. for(i=0;i<n;i++){
  15. scanf("%llu",&arr[i]);
  16. sum+=arr[i];
  17. if(max<arr[i]){
  18. max=arr[i];
  19. }
  20. }
  21. lo=max,hi=sum;
  22. while(lo<hi){
  23. mid=(hi+lo)/2;
  24. // printf("%d \n",mid);
  25. group=getParts(arr,n,mid,k)+1;
  26. // printf("%llu\n",parts+1);
  27. if(group<=k){
  28. hi=mid;
  29. }
  30. else{
  31. lo=mid;
  32. }
  33.  
  34. // printf("lo=%d, hi=%d, mid=%d ,group=%d\n",lo,hi,mid,group);
  35. if(lo+1==hi){
  36. break;
  37. }
  38. }
  39. // for(i=0;i<k-1;i++){
  40. // printf("-%d ",slash[i]);
  41. // }
  42. p=k-2;
  43. for(i=0;i<n;i++){
  44. printf("%llu ",arr[i]);
  45. if(p>=0){
  46. //printf("slash[p]=%d i+1=%d\n",slash[p],i+1);
  47. if(i+1==slash[p]){
  48. printf("/ ");
  49. p--;
  50. }
  51. }
  52. }
  53. // sort(slash);
  54. printf("\n");
  55. }
  56. return 0;
  57. }
  58. int getParts(long long int arr[501],int n,long long int mid,int k){
  59. long long int sum=0,i;
  60. int parts=0;
  61. ind=0;
  62. for(i=n-1;i>=0;i--){
  63. sum+=arr[i];
  64. if(sum>mid){
  65. if(ind<k-1){
  66. slash[ind]=i+1;
  67. ind++;}
  68. parts++;
  69. sum=arr[i];
  70. }
  71. //if(parts)
  72. }
  73. return parts;
  74. }
  75. /*2
  76. 9 3
  77. 1 2 3 4 5 6 7 8 9*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement