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 的最大相鄰斐波那契數。