


2064. Minimiertes Maximum an Produkten, die an jedes Geschäft verteilt werden
Schwierigkeit:Mittel
Themen:Array, Binäre Suche
Sie erhalten eine Ganzzahl n, die angibt, dass es n Fachgeschäfte gibt. Es gibt m Produkttypen mit unterschiedlichen Mengen, die als 0-indizierte ganzzahlige Array-Mengen angegeben werden, wobei Mengen[i] die Anzahl der Produkte des iten Produkttyps darstellt.
Sie müssen alle Produkte unter Einhaltung dieser Regeln an die Einzelhandelsgeschäfte verteilen:
- Einem Shop kann nur höchstens eine Produktart, aber eine beliebige Menge davon gegeben werden.
- Nach der Verteilung erhält jedes Geschäft eine bestimmte Anzahl an Produkten (möglicherweise 0). x sei die maximale Anzahl an Produkten, die einem Geschäft zur Verfügung gestellt werden. Sie möchten, dass x so klein wie möglich ist, d. h. Sie möchten die maximale Anzahl der Produkte, die an ein Geschäft abgegeben werden, minimieren.
Gib das minimal mögliche x zurück.
Beispiel 1:
- Eingabe: n = 6, Mengen = [11,6]
- Ausgabe: 3
-
Erklärung: Ein optimaler Weg ist:
- Die 11 Produkte des Typs 0 werden in diesen Mengen an die ersten vier Filialen verteilt: 2, 3, 3, 3
- Die 6 Produkte des Typs 1 werden in diesen Mengen an die beiden anderen Filialen verteilt: 3, 3
- Die maximale Anzahl an Produkten, die an ein Geschäft abgegeben werden können, beträgt max(2, 3, 3, 3, 3, 3) = 3.
Beispiel 2:
- Eingabe: n = 7, Mengen = [15,10,10]
- Ausgabe: 5
-
Erklärung: Ein optimaler Weg ist:
- Die 15 Produkte des Typs 0 werden in diesen Mengen an die ersten drei Filialen verteilt: 5, 5, 5
- Die 10 Produkte des Typs 1 werden in diesen Mengen an die nächsten beiden Filialen verteilt: 5, 5
- Die 10 Produkte des Typs 2 werden in diesen Mengen an die letzten beiden Filialen verteilt: 5, 5
- Die maximale Anzahl an Produkten, die an ein Geschäft abgegeben werden können, beträgt max(5, 5, 5, 5, 5, 5, 5) = 5.
Beispiel 3:
- Eingabe: n = 1, Mengen = [100000]
- Ausgabe: 100000
-
Erklärung: Der einzig optimale Weg ist:
- Die 100.000 Produkte vom Typ 0 werden an das einzige Geschäft verteilt.
- Die maximale Anzahl an Produkten, die an ein Geschäft abgegeben werden können, beträgt max(100000) = 100000.
Einschränkungen:
- m == Mengen.Länge
- 1 5
- 1 5
Hinweis:
- Es gibt eine monotone Natur, sodass es keine Möglichkeit zum Verteilen gibt, wenn x kleiner als eine bestimmte Zahl ist, und wenn x nicht kleiner als diese Zahl ist, gibt es immer eine Möglichkeit zum Verteilen.
- Wenn Sie eine Zahl k erhalten, bei der die Anzahl der an ein Geschäft abgegebenen Produkte k nicht übersteigt, können Sie dann feststellen, ob alle Produkte verteilt werden können?
- Implementieren Sie eine Funktion canDistribute(k), die „true“ zurückgibt, wenn Sie alle Produkte so verteilen können, dass kein Geschäft mehr als k Produkte erhält, und „false“ zurückgibt, wenn dies nicht möglich ist. Verwenden Sie diese Funktion, um binär nach dem kleinstmöglichen k zu suchen.
Lösung:
Wir können eine binäre Suche nach der maximal möglichen Anzahl von Produkten verwenden, die einem Geschäft zugeordnet sind (x). Hier ist eine Schritt-für-Schritt-Erklärung und die PHP-Lösung:
Ansatz
-
Einrichtung der binären Suche:
- Setzen Sie die Untergrenze (links) auf 1 (da jede Filiale mindestens 1 Produkt erhalten kann).
- Legen Sie die Obergrenze (rechts) als maximale Menge im Mengenarray fest (im schlimmsten Fall erhält ein Geschäft alle Produkte eines Typs).
- Unser Ziel ist es, den Wert von x (maximale Anzahl an Produkten, die an ein Geschäft abgegeben werden) zu minimieren.
-
Binäre Suchlogik:
- Prüfen Sie für jeden Mittelpunkt x, ob es machbar ist, alle Produkte so zu verteilen, dass kein Geschäft mehr als x Produkte hat.
- Verwenden Sie eine Hilfsfunktion canDistribute(x), um die Machbarkeit zu bestimmen.
-
Machbarkeitsprüfung (canDistribute):
- Berechnen Sie für jeden Produkttyp in Mengen die Mindestanzahl an Filialen, die zum Vertrieb dieses Produkttyps erforderlich sind, ohne dass mehr als x Produkte pro Filiale vorhanden sind.
- Summieren Sie die erforderlichen Filialen für alle Produkttypen.
- Wenn die Gesamtzahl der benötigten Filialen kleiner oder gleich n ist, ist die Verteilung mit x als maximaler Belastung pro Filiale möglich; andernfalls ist es nicht machbar.
-
Anpassung der binären Suche:
- Wenn canDistribute(x) „true“ zurückgibt, bedeutet das, dass x eine machbare Lösung ist, aber wir wollen x minimieren, also passen Sie die rechte Grenze an.
- Wenn es „false“ zurückgibt, erhöhen Sie die linke Grenze, da x zu klein ist.
-
Ergebnis:
- Sobald die binäre Suche abgeschlossen ist, enthält links das minimal mögliche x.
Lassen Sie uns diese Lösung in PHP implementieren: 2064. Minimiertes Maximum an Produkten, die an jedes Geschäft verteilt werden
<?php /** * @param Integer $n * @param Integer[] $quantities * @return Integer */ function minimizedMaximum($n, $quantities) { ... ... ... /** * go to ./solution.php */ } /** * Helper function to check if we can distribute products with maximum `x` per store * * @param $x * @param $quantities * @param $n * @return bool */ function canDistribute($x, $quantities, $n) { ... ... ... /** * go to ./solution.php */ } // Test cases echo minimizedMaximum(6, [11, 6]); // Output: 3 echo minimizedMaximum(7, [15, 10, 10]); // Output: 5 echo minimizedMaximum(1, [100000]); // Output: 100000 ?>
Erläuterung:
-
canDistribute-Funktion:
- Für jede Menge werden die mindestens erforderlichen Filialen berechnet, indem die Menge durch x dividiert wird (zum Aufrunden wird die Obergrenze verwendet, da jede Filiale eine ganze Anzahl von Produkten erhalten kann).
- Es wird „false“ zurückgegeben, wenn die kumulierten erforderlichen Speicher n überschreiten.
-
Binäre Suche auf x:
- Die binäre Suche reduziert iterativ den Bereich für x, bis er auf den minimal möglichen Wert konvergiert.
-
Effizienz:
- Diese Lösung ist effizient für große Eingabegrößen (n und m bis zu 10^5), da die binäre Suche in O(log(max_quantity) * m) ausgeführt wird, was innerhalb der gegebenen Einschränkungen möglich ist.
Dieser Ansatz minimiert x und stellt sicher, dass die Produkte so gleichmäßig wie möglich in den Filialen verteilt werden.
Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!
Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:
- GitHub
Das obige ist der detaillierte Inhalt vonMinimiertes Maximum an Produkten, die an jedes Geschäft verteilt werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Lastausgleich beeinflusst das Sitzungsmanagement, kann jedoch durch Sitzungsreplikation, Sitzungsklebrigkeit und zentraler Sitzungsspeicher gelöst werden. 1. Sitzungsreplikationsdaten zwischen Servern. 2. Session Stickiness lenkt Benutzeranfragen auf denselben Server. 3. Zentraler Sitzungsspeicher verwendet unabhängige Server wie Redis, um Sitzungsdaten zu speichern, um die Datenfreigabe zu gewährleisten.

SessionLockingIsatechniqueUTToensureUsers'SSessionSessionSeSexclusivetooneuseratatim.itiscrialtforpreventingDatacorruptionandSecurityBreachesinmulti-UserApplications

Zu den Alternativen zu PHP-Sitzungen gehören Cookies, Token-basierte Authentifizierung, datenbankbasierte Sitzungen und Redis/Memcached. 1. Kookies verwalten Sitzungen, indem sie Daten über den Kunden speichern, was einfach, aber nur gering ist. 2. Altbasierte Authentifizierung verwendet Token, um Benutzer zu überprüfen, was sehr sicher ist, aber zusätzliche Logik erfordert. 3.Database-basiertssesses speichert Daten in der Datenbank, was eine gute Skalierbarkeit aufweist, die Leistung jedoch beeinflusst. V.

Sessionhijacking bezieht sich auf einen Angreifer, der sich als Benutzer ausgibt, indem die SessionID des Benutzers angezeigt wird. Zu den Präventionsmethoden gehören: 1) Verschlüsseln der Kommunikation mit HTTPS; 2) Überprüfung der Quelle der SessionID; 3) mit einem sicheren Algorithmus zur Sitzung der Sitzung; 4) regelmäßig aktualisieren die SitzungID.

In dem Artikel werden PHP erörtert, in dem die vollständige Form, Hauptnutzungen in der Webentwicklung, der Vergleich mit Python und Java und seine Lernen des Lernens für Anfänger beschrieben werden.

PHP behandelt Formdaten mit $ \ _ post und $ \ _ GET Superglobals, wobei die Sicherheit durch Validierung, Bereinigung und sichere Datenbankinteraktionen gewährleistet ist.

Der Artikel vergleicht PHP und ASP.NET und konzentriert sich auf ihre Eignung für groß angelegte Webanwendungen, Leistungsunterschiede und Sicherheitsfunktionen. Beide sind für große Projekte lebensfähig, aber PHP ist Open-Source und plattformunabhängig, während ASP.NET,

Die Fallempfindlichkeit von PHP variiert: Funktionen sind unempfindlich, während Variablen und Klassen empfindlich sind. Zu den Best Practices gehören eine konsistente Benennung und Verwendung von Fall-unempfindlichen Funktionen für Vergleiche.


Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

Video Face Swap
Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

Heiße Werkzeuge

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

SAP NetWeaver Server-Adapter für Eclipse
Integrieren Sie Eclipse mit dem SAP NetWeaver-Anwendungsserver.

Herunterladen der Mac-Version des Atom-Editors
Der beliebteste Open-Source-Editor

SecLists
SecLists ist der ultimative Begleiter für Sicherheitstester. Dabei handelt es sich um eine Sammlung verschiedener Arten von Listen, die häufig bei Sicherheitsbewertungen verwendet werden, an einem Ort. SecLists trägt dazu bei, Sicherheitstests effizienter und produktiver zu gestalten, indem es bequem alle Listen bereitstellt, die ein Sicherheitstester benötigen könnte. Zu den Listentypen gehören Benutzernamen, Passwörter, URLs, Fuzzing-Payloads, Muster für vertrauliche Daten, Web-Shells und mehr. Der Tester kann dieses Repository einfach auf einen neuen Testcomputer übertragen und hat dann Zugriff auf alle Arten von Listen, die er benötigt.

SublimeText3 Linux neue Version
SublimeText3 Linux neueste Version
