Birinchi safar n ta son ko’riladi. Keyin uning taxminan yarmi tashlab yuboriladi va u qism qayta ko’rilmaydi. Demak umumiy amallar soni n+n/2+n/4+… = 2n
Demak bu algoritm ishlash vaqti O(n).
int k_th(int L, int R, int k) { if (L==R) return a[L]; int i = L, j = R; int ind = (L+R) / 2; int X = a[ind]; while (i <= j) { while (a[i] < X) i++;
while (a[j] > X) j--;
if (i <= j) { int t = a[i]; a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
if (k < i-L+1 && k > j-L+1) return a[L+k-1]; if (j-L+1 >= k) return k_th(L, j, k); return k_th(i, R, k-(i-L)); }
int main() { int n, k, b, c, d; cin>>n>>k>>b>>c>>d;
int m = 2147483647; for (int i = 1; i <= n; i++) { a[i] = (int)((1ll*b*i*i+1ll*c*i+d) % m); }
cout<<"\n";
int t1 =clock(); int ans = k_th(1, n, k); cout<int t2 = clock(); cout<<(t2-t1)/1000.0<<"\n";
sort(a+1, a+n+1);
cout<int t3 = clock(); cout<<(t3-t2)/1000.0<<"\n";
return 0; }
Agar har safar o’rtasini emas, balki bu oraliqdagi tasodifiy son olinsa eng optimal algoritm bo’ladi.
ind=L+rand()%(R-L+1) rand() funksiyasi 0 dan 32767 gacha bo’lgan tasodifiy sonni topib beradi. Uni (R-L+1) ga bo’lganda qoldiqni olsak 0 dan R-L gacha tasodifiy son bo’ladi. Uni L ga qo’shsak L dan R gacha tasodifiy son hosil bo’ladi.
Bu funksiya ishlash uchun stdlib.h kutibxona-si zarur.
Struktura va komparator. Birnechta maydonli o’zgaruvchini saqlash uchun strukturadan foydalanamiz. Struktura-ning maydonlari tipi har xil bo’lishi mumkin.
Masalan nuqtani ifodalash uchun ikkita qiymat uning x va y koordinatalari kerak.
