fork(1) download
copy 
  1. //package KLM;
  2. import java.util.*;
  3. import java.lang.*;
  4. import java.io.*;
  5.  
  6. //import KLM.Sonya.InputReader.SpaceCharFilter;
  7. class Copying_Books {
  8.  
  9.  
  10. 	// --------------------------INPUT---------------------------- //
  11. 	static class InputReader {
  12.  
  13. 		private InputStream stream;
  14. 		private byte[] buf = new byte[8192];
  15. 		private int curChar;
  16. 		private int snumChars;
  17. 		private SpaceCharFilter filter;
  18.  
  19. 		public InputReader(InputStream stream) {
  20. 			this.stream = stream;
  21. 		}
  22.  
  23. 		public int snext() {
  24. 			if (snumChars == -1)
  25. 				throw new InputMismatchException();
  26. 			if (curChar >= snumChars) {
  27. 				curChar = 0;
  28. 				try {
  29. 					snumChars = stream.read(buf);
  30. 				} catch (IOException e) {
  31. 					throw new InputMismatchException();
  32. 				}
  33. 				if (snumChars <= 0)
  34. 					return -1;
  35. 			}
  36. 			return buf[curChar++];
  37. 		}
  38.  
  39. 		public int nextInt() {
  40. 			int c = snext();
  41. 			while (isSpaceChar(c))
  42. 				c = snext();
  43. 			int sgn = 1;
  44. 			if (c == '-') {
  45. 				sgn = -1;
  46. 				c = snext();
  47. 			}
  48.  
  49. 			int res = 0;
  50.  
  51. 			do {
  52. 				if (c < '0' || c > '9')
  53. 					throw new InputMismatchException();
  54. 				res *= 10;
  55. 				res += c - '0';
  56. 				c = snext();
  57. 			} while (!isSpaceChar(c));
  58.  
  59. 			return res * sgn;
  60. 		}
  61.  
  62. 		public long nextLong() {
  63. 			int c = snext();
  64. 			while (isSpaceChar(c))
  65. 				c = snext();
  66. 			int sgn = 1;
  67. 			if (c == '-') {
  68. 				sgn = -1;
  69. 				c = snext();
  70. 			}
  71.  
  72. 			long res = 0;
  73.  
  74. 			do {
  75. 				if (c < '0' || c > '9')
  76. 					throw new InputMismatchException();
  77. 				res *= 10;
  78. 				res += c - '0';
  79. 				c = snext();
  80. 			} while (!isSpaceChar(c));
  81.  
  82. 			return res * sgn;
  83. 		}
  84.  
  85. 		public String readString() {
  86. 			int c = snext();
  87. 			while (isSpaceChar(c))
  88. 				c = snext();
  89. 			StringBuilder res = new StringBuilder();
  90. 			do {
  91. 				res.appendCodePoint(c);
  92. 				c = snext();
  93. 			} while (!isSpaceChar(c));
  94. 			return res.toString();
  95. 		}
  96.  
  97. 		public boolean isSpaceChar(int c) {
  98. 			if (filter != null)
  99. 				return filter.isSpaceChar(c);
  100. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  101. 		}
  102.  
  103. 		public interface SpaceCharFilter {
  104. 			public boolean isSpaceChar(int ch);
  105. 		}
  106. 	}
  107. 	//  -------------------------MAIN SOLUTION----------------------------- //
  108.  
  109.  
  110. 	public static void main(String[] args){
  111. 		InputReader in = new InputReader(System.in);
  112. 		int t = in.nextInt();
  113. 		while(t-->0){
  114. 			int n = in.nextInt();
  115. 			int k = in.nextInt();
  116. 			int[] a = new int[n];
  117. 			int mx = Integer.MIN_VALUE;
  118. 			long sum = 0;
  119. 			for(int i =0;i<n;i++){
  120. 				a[i] = in.nextInt();
  121. 				if(a[i]>mx)mx = a[i];
  122. 				sum += a[i];
  123. 			}
  124. 			//ArrayList<Integer> al = new ArrayList<Integer>();
  125. 			long lo = mx;
  126. 			long hi = sum;
  127. 			while(hi-lo>1){
  128. 			//	al.clear();
  129. 				long mid = (hi+lo)/2;
  130. 				int required = 1,current_book = 0;
  131. 				for(int i =0;i<n;i++){
  132. 					if(current_book+a[i] <=mid){
  133. 						current_book+=a[i];
  134. 					}
  135. 					else{
  136. 					//	al.add(current_book);
  137. 						++required;
  138. 						current_book = a[i];
  139. 					}
  140. 				}
  141. 				if(required <= k){
  142. 					hi = mid;
  143. 				}
  144. 				else{
  145. 					lo = mid+1;
  146. 				}
  147. 			}
  148. 		//	here lo is the minimum of maximum books
  149. 		StringBuilder sb = new StringBuilder();
  150. 		sb.append(a[n-1]);
  151. 		sum = a[n-1];
  152. 		k--;
  153. 		for(int i = n-2;i>=0;i--){
  154. 			if(sum+a[i]<=lo && i+1>k){
  155. 				sb.insert(0," ");
  156. 				sum += a[i];
  157. 			}
  158. 			else{
  159. 				sum = a[i];
  160. 				sb.insert(0," / ");
  161. 				k--;
  162. 			}
  163. 			sb.insert(0,a[i]);
  164. 		}
  165. 		System.out.println(sb.toString());
  166.  
  167. 		}
  168. 	}
  169. }
  170.  
Success #stdin #stdout 0.1s 320512KB
comments (?)
stdin
copy 
1 
6 4 
40 40 5 20 10 10
stdout
copy 
40 / 40 / 5 / 20 10 10
https://ideone.com/9xTi5v
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!