Witam, zastanawiam się czy moje rozwiązanie do zadania http://www.spoj.com/problems/AGGRCOW/ jest poprawne.
Chodzi głównie o to, czy nie pominąłem jakichś przypadków (albo w ogóle może logika leży i tego zadania nie rozwiązuje :P, choć dla pierwszych lepszych danych wejściowych jest OK)
oto rozwiązanie:
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
try {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
OutputStream out = new BufferedOutputStream(System.out);
int n = Integer.parseInt(in.readLine());
for (int i = 0; i < n; ++i) {
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int ncows = Integer.parseInt(tokenizer.nextToken());
int c = Integer.parseInt(tokenizer.nextToken());
int[] cows = new int[ncows];
for (int j = 0; j < ncows; ++j) {
cows[j] = Integer.parseInt(in.readLine());
}
Arrays.sort(cows);
int low = 0;
int high = ncows - 1;
int max = (cows[high] + cows[low]) / (c - 1);
if (c == 2) {
max = cows[high] - cows[low];
out.write((max + "\n").getBytes());
continue;
}
int found = Integer.MAX_VALUE;
for (int k = 0; k < ncows; ++k) {
if (Math.abs(cows[k] - max) < Math.abs(found - max)) {
found = cows[k];
if (found == max) {
break;
}
}
}
if (found > cows[low]) {
max = Math.min(found - cows[low], Math.abs(found - cows[high]));
} else {
max = found;
}
out.write((max + "\n").getBytes());
}
out.flush();
} catch (IOException e) {
return;
}
}
}