fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. import static java.lang.Math.max;
  4. import static java.lang.Math.min;
  5. class Main
  6. {
  7. 	static class FastReader {
  8.         BufferedReader br;
  9.         StringTokenizer st;
  10.  
  11.         public FastReader() {
  12.             br = new BufferedReader(new InputStreamReader(System.in));
  13.         }
  14.  
  15.         String next() {
  16.             while (st == null || !st.hasMoreTokens()) {
  17.                 try {
  18.                     st = new StringTokenizer(br.readLine());
  19.                 } catch (IOException e) {
  20.                     e.printStackTrace();
  21.                 }
  22.             }
  23.             return st.nextToken();
  24.         }
  25.  
  26.         int nextInt() {
  27.             return Integer.parseInt(next());
  28.         }
  29.  
  30.         long nextLong() {
  31.             return Long.parseLong(next());
  32.         }
  33.  
  34.         double nextDouble() {
  35.             return Double.parseDouble(next());
  36.         }
  37.  
  38.         String nextLine() {
  39.             String str = "";
  40.             try {
  41.                 str = br.readLine().trim();
  42.             } catch (Exception e) {
  43.                 e.printStackTrace();
  44.             }
  45.             return str;
  46.         }
  47.     }
  48.  
  49.     static class FastWriter {
  50.         private final BufferedWriter bw;
  51.  
  52.         public FastWriter() {
  53.             this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
  54.         }
  55.  
  56.         public void print(Object object) throws IOException {
  57.             bw.append("" + object);
  58.         }
  59.  
  60.         public void println(Object object) throws IOException {
  61.             print(object);
  62.             bw.append("\n");
  63.         }
  64.  
  65.         public void close() throws IOException {
  66.             bw.close();
  67.         }
  68.     }
  69. 	public static void main (String[] args) throws java.lang.Exception
  70. 	{
  71. 		 try {
  72.             FastReader fin = new FastReader();
  73.             FastWriter fout = new FastWriter();
  74.                 int t = fin.nextInt();
  75.                 while(t-- > 0) {
  76.                 int n = fin.nextInt();
  77.                 int cows = fin.nextInt();
  78.                 long[] barns = new long[n];
  79.                 long maxCordinate = Long.MIN_VALUE;
  80.                 long minCordinate = Long.MAX_VALUE;
  81.                 for (int i = 0; i < n; i++) {
  82.                     barns[i] = fin.nextLong();
  83.                     maxCordinate = max(maxCordinate, barns[i]);
  84.                     minCordinate = min(minCordinate,barns[i]);
  85.                 }
  86.                 Arrays.sort(barns);
  87.                 long start = 1;
  88.                 long end = maxCordinate - minCordinate;
  89.                 while(start <= end) {
  90.                     long mid = (end-start)/2 + start;
  91.                     if(canWePlaceCows(mid,cows,barns)){
  92.                         start =mid+1;
  93.                     }
  94.                     else {
  95.                         end = mid-1;
  96.                     }
  97.                 }
  98.                 fout.println(end);
  99.              }
  100.  
  101.             fout.close();
  102.         } catch (Exception e) {
  103.             e.printStackTrace();
  104.             return;
  105.         }
  106. 	}
  107. 	    private static boolean canWePlaceCows(long mid, int cows, long[] barns) {
  108.         int currentCntCows = 1;
  109.         long lastCow = barns[0];
  110.         for(int i = 1;i<barns.length;i++){
  111.             if(barns[i]-lastCow >= mid){
  112.                 currentCntCows++;
  113.                 lastCow = barns[i];
  114.             }
  115.             if(currentCntCows == cows){
  116.                 return true;
  117.             }
  118.         }
  119.         return false;
  120.     }
  121. }
Success #stdin #stdout 0.12s 57824KB
comments (?)
stdin
copy 
1
5 3
1
2
8
4
9
stdout
copy 
3
https://ideone.com/OOdH1G
problem AGGRCOW, based on SPOJ submission 35135438 (JAVA), 2025-10-25 21:23:42
language:
Java (HotSpot 12)
created:
9 days 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!