SPOJ 297 — Aggressive cows (CODE: AGGRCOW)
求最大值最小,快排+二分答案.
水题,不写题解.
1Y了,比较兴奋.
此题正好练习二分答案.发现在SPOJ上看别人AC哪道就做哪道也不是难事…
不过这道题才0.1分…
{
SPOJ 297; Aggressive Cows; AGGRCOW
- sqybi’s code
- 快排+二分答案
}
//for my winsty
program aggrcow_sqybi;
const
nn = 100000;
var
cases, times, n, m, max, l, r, mid, ans, i: longint;
a: array[1..nn]of longint;
procedure qsort(l, r: longint);
var
i, j, d, t: longint;
begin
i := l;
j := r;
d := a[(l+r) div 2];
repeat
while a[l] < d do inc(l);
while a[r] > d do dec(r);
if l <= r then begin
t := a[l];
a[l] := a[r];
a[r] := t;
inc(l);
dec(r);
end;
until l > r;
if l < j then qsort(l, j);
if i < r then qsort(i, r);
end;
function check(x: longint): boolean;
var
s, t, i: longint;
begin
s := 1;
t := 2;
i := 1;
while t <= n do begin
if i = m then break;
if a[t] - a[s] >= x then begin
inc(i);
s := t;
end;
inc(t);
end;
check := i = m;
end;
begin
readln(cases);
for times:=1 to cases do begin
readln(n, m);
max := -1;
for i:=1 to n do begin
readln(a[i]);
if a[i] > max then max := a[i];
end;
if n > 1 then qsort(1, n);
l := 1;
r := max;
ans := 0;
repeat
if l > r then break;
mid := (l + r) div 2;
if check(mid) then begin
ans := mid;
l := mid + 1;
end
else
r := mid - 1;
until false;
writeln(ans);
end;
end.
阅读(117 次)