237
Se dă un șir a[1]
, a[2]
, …, a[n]
de numere naturale și un număr natural k
.
Cerința
Să se determine cele mai mari k
numere din șir.
Date de intrare
Programul citește de la tastatură numerele n
, k
, A
, B
, C
, D
. Șirul de numere se va genera după formulele:
a[1] = A
a[i] = (B * a[i-1] + C) % D
, pentrui=2..n
Date de ieșire
Programul va afișa pe ecran, ordonate crescător, cele mai mari k
numere din șir.
Restricții și precizări
1 ≤ n ≤ 5.000.000
1 ≤ k ≤ min(100.000, n)
1 ≤ A, B, C, D ≤ 1.000.000.000
Exemplu
Intrare
10 4 13 23 47 97
Ieșire
55 56 74 96
Explicație
Se obține șirul de numere a = (13, 55, 51, 56, 74, 3, 19, 96, 24, 17)
. Cele mai mari patru numere sunt 55
, 56
, 74
, 96
.
#include <bits/stdc++.h> using namespace std; int n, H[100001], k; long long a, b, c, d; void push_up(int k){ while(k > 1){ if(H[k] >= H[k / 2]) return ; else swap(H[k], H[k / 2]), k /= 2; } } void push_down(int k, int n){ while(2 * k <= n){ int p = 2 * k; if(p + 1 <= n && H[p + 1] < H[p]) p++; if(H[k] <= H[p]) return ; else swap(H[p], H[k]), k = p; } } int main(){ cin >> n >> k >> a >> b >> c >> d; H[1] = a; for(int i = 2; i <= n; ++i){ a = (1ll * a * b + c) % d; if(i > k){ if(a > H[1]) H[1] = a, push_down(1, k); } else H[i] = a, push_up(i); } while(k > 0){ cout << H[1] << ' '; H[1] = H[k]; k--; push_down(1, k); } return 0; }
Comentarii