K-èsim element P63584


Statement
 

pdf   zip   main.cc

html

Usant les definicions

typedef vector<int> VE; typedef vector<VE> VVE;

implementeu una funció

int k_esim(int k, const VVE& V);

que retorni el k-èsim element global (començant en u) dels elements continguts en el vector de vectors V. Sigui n = V.size(). Cal tenir en compte que, per a tota 0 ≤ i < n, V[i] està ordenat de petit a gran. A més, no hi ha cap element repetit en tot V.

Per exemple, si k = 5, n = 3, i els tres vectors són

|| V[0]

121015


V[1]

-5-312


V[2]

034620

||

llavors la resposta és 2, que és el cinquè element més petit de tots els vectors.

Sigui m = ∑0n−1 V[i].size(). Podeu suposar que k està entre 1 i m, que n està entre 2 i 500, i que algun V[i] pot estar buit. Si us cal, podeu implementar procediments auxiliars. Tingueu en compte que, en els jocs de proves “grossos”, k = Θ(n) i m = Θ(n2). La solució esperada en aquest cas té cost Θ(n logn).

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Information
Author
Enric Rodríguez
Language
Catalan
Other languages
English
Official solutions
C++
User solutions
C++