第K极值 pascal

第K极值 pascal
第K极值 pascal

第K极值 pascal
program kth;
var
a:array[1..10000] of longint;
k,i,j,n,m,h:longint;
procedure qsort(s,t:longint);
var
i,j,x,temp:longint;
begin
i:=s;j:=t;x:=a[(i+j) div 2];
repeat
while a[i]x do dec(j);
if ij;
if s

呵呵.. tyvj 第K极值?
下面代码是很早很早写的.你将就着吧 O(nlgn)的复杂..
如果你想要O(n)的算法.可以HI我
program e2;
var
a:array[1..10000]of longint;
n,k,i,res:longint;
procedure paixu(x,y:longint);
var

全部展开

呵呵.. tyvj 第K极值?
下面代码是很早很早写的.你将就着吧 O(nlgn)的复杂..
如果你想要O(n)的算法.可以HI我
program e2;
var
a:array[1..10000]of longint;
n,k,i,res:longint;
procedure paixu(x,y:longint);
var
i,j,t,m:longint;
begin
i:=x;
j:=y;
m:=(a[x]+a[y])div 2;
repeat
while a[i] while a[j]>m do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i if xend;
function work(t:longint):boolean;
var
i:longint;
begin
work:=true;
if t<=1 then exit(false);
for i:=2 to trunc(sqrt(t)) do
if t mod i = 0 then work:=false;
end;
begin
readln(n,k);
for i:=1 to n do
read(a[i]);
paixu(1,n);
res:=a[n+1-k]-a[k];
if work(res) then
writeln('YES')
else
writeln('NO');
writeln(res);
end.

收起

Vijos compatible layer: 1.2 build 100204
Judge status: Accepted
VijosNT Judger: 1.2 build 100318
Compiler: Free Pascal
fpc -O2 -g -otest.exe test.pas
Test #1: Accepted... 0ms<...

全部展开

Vijos compatible layer: 1.2 build 100204
Judge status: Accepted
VijosNT Judger: 1.2 build 100318
Compiler: Free Pascal
fpc -O2 -g -otest.exe test.pas
Test #1: Accepted... 0ms
Test #2: Accepted... 0ms
Test #3: Accepted... 0ms
Test #4: Accepted... 0ms
Test #5: Accepted... 0ms
Test #6: Accepted... 0ms
Test #7: Accepted... 0ms
Test #8: Accepted... 0ms
Test #9: Accepted... 0ms
Test #10: Accepted... 0ms
Total score: 100, time usage: 0ms
var
q,i,n,k:longint;
a:array[0..10000]of longint;
procedure qp(l,r:longint);
var
x,y,mid:longint;
begin
x:=l;y:=r;mid:=a[(l+r)div 2];
repeat
while a[x]while a[y]>mid do dec(y);
if x<=y then
begin
q:=a[x];a[x]:=a[y];a[y]:=q;
inc(x);dec(y);
end;
until x>y;
if xif y>l then qp(l,y);
end;
begin
read(n,k);
for i:=1 to n do
read(a[i]);
qp(1,n);
q:=a[n-k+1]-a[k];
if q<2 then begin writeln('NO');writeln(q);halt;end;
if q=2 then begin writeln('YES');writeln(q);halt;end;
for i:=2 to trunc(sqrt(q)) do
if q mod i=0 then begin writeln('NO');writeln(q);halt;end;
writeln('YES');
writeln(q);
end.

收起