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