ho un insieme di n elementi per la precisione ogni elemento è un pair di due interi ; bisogna prendere k elementi e massimizzare il risultato dell espressione :
sommatoria del .first di ogni elemento selezionato / la sommatoria del .second
https://codeforces.com/edu/course/2/lesson/6/4/practice/contest/285069/problem/C
essendo che ho appena incominciato con i problemi bs e per quanto ho capito la spiegazione; non mi ha aiutato a dare una soluzione inferiore all esponenziale non capisco come si può risolvere questo problema in binary search non mi viene nulla in mente al di fuori di una esponenziale
Vogliamo massimizzare il rapporto \displaystyle\frac{a_{i1}+a_{i2}+\ldots+a_{ik}}{b_{i1}+b_{i2}+\ldots+b_{ik}}.
Facciamo una ricerca binaria sul valore di questo rapporto, vogliamo verificare che questo rapporto sia maggiore di x:
\begin{align}
\displaystyle\frac{a_{i1}+a_{i2}+\ldots+a_{ik}}{b_{i1}+b_{i2}+\ldots+b_{ik}}&>x \\
a_{i1}+a_{i2}+\ldots+a_{ik}&>x\cdot\left(b_{i1}+b_{i2}+\ldots+b_{ik}\right) \\
a_{i1}+a_{i2}+\ldots+a_{ik}&>x\cdot b_{i1}+x\cdot b_{i2}+\ldots+x\cdot b_{ik} \\
(a_{i1}-x\cdot b_{i1})+(a_{i2}-x\cdot b_{i2})+\ldots+(a_{ik}-x\cdot b_{ik})&>0 \\
\end{align}
Quindi creiamo un array dove c_i=a_i-x\cdot b_i e usiamo std::sort oppure std::nth_element per trovare i k valori più grandi e infine verifichiamo che la somma di questi valori sia positiva.
2 Mi Piace