Posició d'inserció més a la dreta P54070


Statement
 

pdf   zip   main.cc

html

Escriviu una funció eficient

int mes_a_la_dreta(double x, const vector<double>& v);

que retorni la posició més a la dreta on x podria ser inserit en el vector ordenat v (afegint una posició al final de v i movent els elements que calgui una posició cap a la dreta) de manera que v romangui ordenat.

Per exemple, assumiu que x és 23. Si v és [15, 15, 20, 30, 40, 40], hauríem d’inserir x a la posició 3 (entre 20 i 30), i el v resultant seria [15, 15, 20, 23, 30, 40, 40]. Si v és [17, 23, 23, 35, 42, 42], podríem inserir x a les posicions 1, 2 o 3, així que la vostra funció ha de retornar 3. Si v és [3, 5, 7, 9], x hauria de ser inserit a la posició just a la dreta del final del vector, això és, 4. Com a exemple final, si v és [23, 23], x hauria de ser inserit a 2.

Precondició

El vector v està ordenat en ordre no-decreixent.

Observacions

  • La vostra solució només pot usat la llibreria vector.
  • Podeu escriure i usar funcions addicionals si us calen.
  • Només cal enviar el procediment requerit; el programa principal serà ignorat.
Information
Author
Salvador Roura
Language
Catalan
Other languages
English
Official solutions
C++
User solutions
C++