Contractació P21012
Una companyia vol contractar nous treballadors. La companyia ha ordenat els n candidats de més valuosos a menys valuosos. Per a cada candidat i, saben el sou si que demana. Volen triar els candidats de manera que si un candidat és més valuós que un altre, cobri estrictament més. Quina és la màxima quantitat de nous treballadors que es pot contractar?
Entrada
L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 105, seguida de s1, …, sn. Totes les si estan entre 1 i 109.
Sortida
Per a cada cas, escriviu quants treballadors es podran contractar.
Observació
La solució esperada té cost millor que Θ(n2).
Public test cases
Input
1 100 3 42 42 42 2 1000000000 1 8 23 16 19 5 12 16 12 10
Output
1 1 2 5
Information
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++