fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Collection;
  6. import java.util.TreeMap;
  7.  
  8. public class Main {
  9.  
  10. 	public static void main(String[] args) {
  11. 		try {
  12. 			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13. 			int t = Integer.parseInt(br.readLine());
  14. 			int n = 0, k = 0;
  15. 			String key = null;
  16. 			Integer value = 0;
  17. 			TreeMap<String, Integer> table = new TreeMap<String, Integer>();
  18. 			String data[] = null;
  19.  
  20. 			for (int i = 0; i < t; i++) {
  21.  
  22. 				data = br.readLine().split(" ");
  23. 				n = Integer.parseInt(data[0]);
  24. 				k = Integer.parseInt(data[1]);
  25.  
  26. 				data = br.readLine().split(" ");
  27. 				if(k==1){
  28. 					System.out.println(0);
  29. 					continue;
  30. 				}
  31. 				for (int j = 0; j < n; j++) {
  32. 					key =data[j].trim();
  33. 					value = table.get(key);
  34. 					if (value == null) {
  35. 						value = 0;
  36.  
  37. 					}
  38. 					value++;
  39. 					value = value % k;
  40. 					table.put(key, value);
  41.  
  42. 				}
  43. 				Collection<Integer> boquey = table.values();
  44. 				ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
  45.  
  46. 				long result = 0L;
  47. 				int len=heights.size();
  48. 				int req=0;
  49. 				int freePool=heights.get(len-1);
  50. 				int j=0;
  51. 				for( j=len-1;j>=0;j--){
  52. 					if(heights.get(j)!=0){
  53. 						freePool=heights.get(j);
  54. 						break;
  55. 					}
  56. 				}
  57. 				j--;
  58. 				int current=0;
  59. 				int limit=0;
  60. 				for( ;j>0;j--){
  61. 					if(heights.get(j)==0){
  62. 						continue;
  63. 					}
  64. 					current=heights.get(j);
  65. 					req=k-current;
  66. 					limit=k/2;
  67. 					if(k%2!=0){
  68. 						limit++;
  69. 					}
  70. 					if(req<=freePool&&current>=limit){
  71. 						result+=req;
  72. 						freePool-=req;
  73. 					}else{
  74. 						freePool+=current;
  75. 					}
  76. 				}
  77. 				result+=freePool;
  78. 				table.clear();
  79. 				System.out.println(result);
  80. 			}
  81. 		} catch (IOException ex) {
  82. 		}
  83.  
  84. 	}
  85.  
  86. }
Success #stdin #stdout 0.05s 711168KB
comments (?)
stdin
copy 
1
16 4
442 55 19 865 22 878 689 67 532 419 476 33 244 473 424 945
stdout
copy 
15
https://ideone.com/qLNCNJ
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!