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.HashMap;
  7.     import java.util.Iterator;
  8.     import java.util.Set;
  9.     import java.util.TreeMap;
  10.  
  11.     public class Main {
  12.  
  13.     	public static void main(String[] args) {
  14.     		try {
  15.     			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  16.     			int t = Integer.parseInt(br.readLine());
  17.     			int n = 0, k = 0;
  18.     			String key = null;
  19.     			Integer value = 0, reqCnt = 0, demand = 0;
  20.     			TreeMap<String, Integer> table = new TreeMap<String, Integer>();
  21.     			HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
  22.     			String data[] = null;
  23.  
  24.     			for (int i = 0; i < t; i++) {
  25.     				reqCntTable.clear();
  26.     				table.clear();
  27.     				data = br.readLine().split(" ");
  28.     				n = Integer.parseInt(data[0]);
  29.     				k = Integer.parseInt(data[1]);
  30.  
  31.     				data = br.readLine().split(" ");
  32.     				if (k == 1) {
  33.     					System.out.println(0);
  34.     					continue;
  35.     				}
  36.     				for (int j = 0; j < n; j++) {
  37.     					key = data[j].trim();
  38.     					value = table.get(key);
  39.     					if (value == null) {
  40.     						value = 0;
  41.  
  42.     					}
  43.     					value++;
  44.     					value = value % k;
  45.     					table.put(key, value);
  46.  
  47.  
  48.     				}
  49.     				Collection<Integer> boquey = table.values();
  50.     				ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
  51.     				int hlen=heights.size();
  52.  
  53.     				Set keys=table.keySet();
  54.     				Iterator iterator=keys.iterator();
  55.     				String keyStr="";
  56.  
  57.     				while(iterator.hasNext()){
  58.     					keyStr=(String) iterator.next();
  59.     					demand = (k -table.get(keyStr));
  60.     					reqCnt = reqCntTable.get(demand);
  61.     					if (reqCnt == null) {
  62.     						reqCnt = 1;
  63.     					}else{
  64.     						reqCnt++;
  65.     					}
  66.     					reqCntTable.put(demand, reqCnt);
  67.     				}
  68.  
  69.  
  70.     				long result = 0L;
  71.     				int len = heights.size();
  72.     				int freePool = 0, cpool = 0;
  73.     				Integer available = 0;
  74.     				int j = 0;
  75.     				int bqCnt=0;
  76.     				int reqAux = 0;
  77.  
  78.     				for (j = len - 1; j > 0; j--) {
  79.     					cpool = heights.get(j);
  80.     					reqAux = k - cpool;
  81.     					available = reqCntTable.get(cpool);
  82.     					if ((available != null) && (available >0)) {
  83.     						int index=heights.indexOf(reqAux);
  84.     						heights.set(index, 0);
  85.     						result+=cpool;
  86.     						available--;
  87.     						reqCntTable.put(cpool, available);
  88.     						reqAux = k - cpool;
  89.     						available = reqCntTable.get(reqAux);
  90.     						available--;
  91.     						reqCntTable.put(reqAux, available);
  92.     					}else{
  93.     						freePool += cpool;
  94.     						bqCnt=freePool/k;
  95.     						freePool=freePool%k;
  96.     						result+=(k-1)*bqCnt;
  97.     					}
  98.     				}
  99.  
  100.     				bqCnt=freePool/k;
  101.     				freePool=freePool%k;
  102.     				result+=(k-1)*bqCnt;
  103.  
  104.     				result += freePool;
  105.     				table.clear();
  106.     				System.out.println(result);
  107.     			}
  108.     		} catch (IOException ex) {
  109.     		}
  110.  
  111.     	}
  112.  
  113.     }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
1
12 4
1 2 3 4 4 5 6 7 8 9 10 11
stdout
copy 
9
https://ideone.com/ClX4Ql
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

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!