K 极值帕斯卡 20

呵呵。 tyvj kth extremum？

下面的**是很早就写的。 你要去 o（nlgn） 复合体。

如果你想要一个 o（n） 的算法。 可以嗨我。

program e2;

vara:array[1..10000]of longint;

n,k,i,res:longint;

procedure paixu(x,y:longint);

vari,j,t,m:longint;

begini:=x;

j:=y;m:=(a[x]+a[y])div 2;

repeat

while a[i]m do dec(j);

if i<=j then

begint:=a[i];

a[i]:=a[j];

a[j]:=t;

inc(i);

dec(j);

end;until i>j;

if iif xend;function work(t:longint):boolean;

vari:longint;

beginwork:=true;

if t<=1 then exit(false);

for i:=2 to trunc(sqrt(t)) doif 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')

elsewriteln('no');

writeln(res);

end.

program kth;

vara:array[1..10000] of longint;

k,i,j,n,m,h:longint;

procedure qsort(s,t:longint);

vari,j,x,temp:longint;

begini:=s;j:=t;x:=a[(i+j) div 2];

repeat

while a[i]x do dec(j);

if i<=j then

begintemp:=a[i];a[i]:=a[j];a[j]:=temp;

inc(i);dec(j);

end;until i>j;

if sif iend;function pd(a:longint):boolean;

vari:longint;

beginif a<=1 then exit(false);

for i:=2 to trunc(sqrt(a)) doif a mod i =0 then exit(false);

exit(true);

end;begin

readln(n,k);

for i:=1 to n do read(a[i]);

qsort(1,n);

h:=a[k];j:=a[n-k+1];

m:=j-h;

if pd(m)=true then

beginwriteln('yes');

writeln(m);

endelse

beginwriteln('no');

writeln(m);

end;end.

你能读懂吗？ 我不明白嗨，我！

vara:array[0..100001] of longint;

i,j,k,n,max,min:longint;

function su(x:longint):boolean;

var i:longint;

beginif x<=1 then exit(false);

for i:=2 to trunc(sqrt(x)) doif x mod i=0 then exit(false);

exit(true);

end;procedure kuai(l,r:longint);

var i,j,k,t:longint;

begini:=l;

j:=r;k:=a[(i+j) div 2];

repeat

while a[i]k do dec(j);

if i<=j then

begint:=a[i];

a[i]:=a[j];

a[j]:=t;

inc(i);

dec(j);

end;until i>j;

if iif lend;

beginreadln(n,k);

for i:=1 to n do

read(a[i]);

kuai(1,n);

min:=a[k];

max:=a[n-k+1];

if su(max-min) then

beginwriteln('yes');

writeln(max-min);

endelse

beginwriteln('no');

writeln(max-min);

end;end.

虽然我不是tyvj的创始人，易水知寒，但我偷了他老人家的程序。 在这里向他道歉......

总的来说，这个问题的想法比较清楚。

首先，我们对读取的数据进行排序，从小到大得到 n 个数字。 则第 k 个最小数是字符串中的第 k 个数，第 k 个最大数是 n-k+1，即倒数第 k 个数，减去得到差。 然后你就可以判断质数了。

vara:array[0..10010] of longint;

i,t,n,k:longint;

procedure qsort(r,l:longint);

vari,j,mid,t:longint;

begini:=r; j:=l;

mid:=a[(i+j)>>1];

repeat

while a[i]mid do j:=j-1;

if i<=j then

begint:=a[i]; a[i]:=a[j]; a[j]:=t;

i:=i+1; j:=j-1;

end;until i>j;

if iif rend;begin

readln(n,k);

for i:=1 to n do read(a[i]);

qsort(1,n);因为 n 有 10000，所以不能使用普通的 n 2 排序，需要使用 nlogn 排序。 例如，我们现在使用的快速排序。 关于这个排序，因为本文的重点和文章长度之间的关系。 详情请咨询您自己。

t:=abs(a[n-k+1]-a[k]);如上所述。 因为不能保证第 k 个最大值大于第 k 个小值，所以应取绝对值，即 abs。 其中 abs（x） 表示 x 的绝对值。

对于 i：=2 到 trunc（sqrt（t）） 确实枚举所有可以被 t 整除的数字。 显然，得到根数 t 就足够了。 请自行弥补。

if t mod i=0 then

beginwriteln('no');

writeln(t);

halt;直接退出程序。

end;writeln('yes');

writeln(t);

end.

大哥，你不赋值初始值，当m=1时，q的值是不确定的。 所以它应该在开始后添加。

q:=false;

那。。。。。。

我是《......》的作者

也就是说，tyvj 的管理员......

首先，使用快速排序（因为数据号称是10w，悄悄地告诉你......事实上，最大值只有 100 ......当时我们学校模拟了比赛，数据是临时出来的，所以......）

让我在上面做个记号。

vara:array[0..100001] of longint;

i,j,k,n,max,min:longint;

function su(x:longint):boolean;

var i:longint;

beginif x<=1 then exit(false);

for i:=2 to trunc(sqrt(x)) doif x mod i=0 then exit(false);

exit(true);

end;procedure kuai(l,r:longint);

var i,j,k,t:longint;

begini:=l;

j:=r;k:=a[(i+j) div 2];

repeat

while a[i]k do dec(j);

if i<=j then

begint:=a[i];

a[i]:=a[j];

a[j]:=t;

inc(i);

dec(j);

end;until i>j;

if iif lend;

beginreadln(n,k);

for i:=1 to n do

read(a[i]);

kuai(1,n);

min:=a[k];

max:=a[n-k+1];

if su(max-min) then

beginwriteln('yes');

writeln(max-min);

endelse

beginwriteln('no');

writeln(max-min);

end;end.

文笔还是比较简洁的......

......关于您的计划

if t<2 then begin writeln('no'); halt; end;

看来......这将在の之后输出一些东西

看：其余的似乎都没问题......

TYVJ官方***20517473欢迎您加入............入睡

10W 数据 n 2 的效率肯定会超时。

过程 qsort（l，r：longint）;

varq,p,mid,temp:longint;

beginq:=l; p:=r; mid:=a[random(r-l)+l];

repeat

while a[q]mid do dec(p);

if q<=p then

begintemp:=a[q];

a[q]:=a[p];

a[p]:=temp;

inc(q); dec(p);

end;until q>p;

if lif qend;

然后+讨论两个数字之间的差值是否大于 0，你可以通过它。

我的意见，让我们把它交给广告（Hanhan）。

快速行 获取数组中的数据。

在经典问题中，我们首先需要证明 m 和 n 在斐波那契数列中是相邻的两个。 首先，证明斐波那契数列中的两个相邻项满足方程（2），这很简单，可以用数学方法完成。 进一步证明，如果两个正整数 m 和 n 满足方程 （2），则一定有 n>=m，并且整数 n-m 和 m 也满足方程 （2）（其中正整数对是有序的）。

因此，我们可以继续这样看：（m，n）=>n-m，m）=>2m-n，n-m）=>

直到括号中的两个数字相等（如果首先有 m=n，则无需查找）。 很容易证明，如果两个相等的正整数满足方程（2），那么它们都等于1。 我们可以倒过来找到它：

1,1）<=1,2）<=2,3）<=直到它返回（m，n）。所以 m 和 n 在斐波那契数列中彼此相邻。

剩下的很简单：找到两个小于 k 的最大相邻斐波那契数。