. Introduction en bourse-tutoriel php-php.cn

. IPO

502. Introduction en bourse

Dur

Supposons que LeetCode commence bientôt sonIPO. Afin de vendre à bon prix ses actions à Venture Capital, LeetCode souhaiterait travailler sur quelques projets d'augmentation de capital avant l'IPO. Comme ses ressources sont limitées, elle ne peut terminer qu'un maximum de k projets distincts avant l'IPO. Aidez LeetCode à concevoir la meilleure façon de maximiser son capital total après avoir terminé au plus k projets distincts.

Vous recevez n projets où le i^èmeprojet a un pur profit[i] et un capital minimum de capital[i] est nécessaire pour le démarrer.

Au départ, vous avez w capital. Lorsque vous terminerez un projet, vous obtiendrez son profit pur et le profit sera ajouté à votre capital total.

Choisissez une liste deau plusk projets distincts à partir de projets donnés pourmaximiser votre capital final, et restituezle capital final maximisé.

Il est garanti que la réponse tient dans un entier signé de 32 bits.

Exemple 1 :

Entrée :k = 2, w = 0, bénéfices = [1,2,3], capital = [0,1,1]
Sortie :4
Explication :Puisque votre capital initial est de 0, vous ne pouvez démarrer le projet qu'indexé 0.

Après l'avoir terminé, vous obtiendrez un bénéfice de 1 et votre capital deviendra 1.

Avec le majuscule 1, vous pouvez soit démarrer le projet indexé 1, soit le projet indexé 2.

Puisque vous pouvez choisir au maximum 2 projets, vous devez terminer le projet indexé 2 pour obtenir le capital maximum.

Par conséquent, extrayez le capital final maximisé, qui est 0 + 1 + 3 = 4.

Exemple 2 :

Entrée :k = 3, w = 0, bénéfices = [1,2,3], capital = [0,1,2]
Sortie :6

Contraintes :

1 <= k <= 10⁵
0 <= w <= 10⁹
n == profits.longueur
n == capital.length
1 <= n <= 10⁵
0 <= bénéfices[i] <= 10⁴
0 <= majuscule[i] <= 10⁹

Solution :

class Solution { /** * @param Integer $k * @param Integer $w * @param Integer[] $profits * @param Integer[] $capital * @return Integer */ function findMaximizedCapital($k, $w, $profits, $capital) { $n = count($capital); $minCapitalHeap = new SplMinHeap(); for ($i = 0; $i < $n; ++$i) { $minCapitalHeap->insert([$capital[$i], $profits[$i]]); } $maxProfitHeap = new SplMaxHeap(); while ($k-- > 0) { while (!$minCapitalHeap->isEmpty() && $minCapitalHeap->top()[0] <= $w) { $maxProfitHeap->insert($minCapitalHeap->extract()[1]); } if ($maxProfitHeap->isEmpty()) { break; } $w += $maxProfitHeap->extract(); } return $w; } }Liens de contact
        
         LinkedIn
         GitHub
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!