K-èsim element P63584

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 \le 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

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

Sigui $m = \sum_0^{n-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 = \Theta(n)$ i $m = \Theta(n^2)$. La solució esperada en aquest cas té cost $\Theta(n \log n)$.

Observació

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