suchen
HeimBackend-EntwicklungPHP-TutorialMinimiertes Maximum an Produkten, die an jedes Geschäft verteilt werden

Minimized Maximum of Products Distributed to Any Store

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:

  1. 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.
  2. 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?
  3. 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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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:

  1. 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.
  2. 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.
  3. 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:

  • LinkedIn
  • 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!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Arbeiten mit Flash -Sitzungsdaten in LaravelArbeiten mit Flash -Sitzungsdaten in LaravelMar 12, 2025 pm 05:08 PM

Laravel vereinfacht die Behandlung von temporären Sitzungsdaten mithilfe seiner intuitiven Flash -Methoden. Dies ist perfekt zum Anzeigen von kurzen Nachrichten, Warnungen oder Benachrichtigungen in Ihrer Anwendung. Die Daten bestehen nur für die nachfolgende Anfrage standardmäßig: $ Anfrage-

Curl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIsCurl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIsMar 14, 2025 am 11:42 AM

Die PHP Client -URL -Erweiterung (CURL) ist ein leistungsstarkes Tool für Entwickler, das eine nahtlose Interaktion mit Remote -Servern und REST -APIs ermöglicht. Durch die Nutzung von Libcurl, einer angesehenen Bibliothek mit Multi-Protokoll-Dateien, erleichtert PHP Curl effiziente Execu

Vereinfachte HTTP -Reaktion verspottet in Laravel -TestsVereinfachte HTTP -Reaktion verspottet in Laravel -TestsMar 12, 2025 pm 05:09 PM

Laravel bietet eine kurze HTTP -Antwortsimulationssyntax und vereinfache HTTP -Interaktionstests. Dieser Ansatz reduziert die Code -Redundanz erheblich, während Ihre Testsimulation intuitiver wird. Die grundlegende Implementierung bietet eine Vielzahl von Verknüpfungen zum Antworttyp: Verwenden Sie Illuminate \ Support \ facades \ http; Http :: fake ([ 'Google.com' => 'Hallo Welt',, 'github.com' => ['foo' => 'bar'], 'Forge.laravel.com' =>

PHP -Protokollierung: Best Practices für die PHP -ProtokollanalysePHP -Protokollierung: Best Practices für die PHP -ProtokollanalyseMar 10, 2025 pm 02:32 PM

Die PHP -Protokollierung ist für die Überwachung und Debugie von Webanwendungen von wesentlicher Bedeutung sowie für das Erfassen kritischer Ereignisse, Fehler und Laufzeitverhalten. Es bietet wertvolle Einblicke in die Systemleistung, hilft bei der Identifizierung von Problemen und unterstützt eine schnellere Fehlerbehebung

12 Beste PHP -Chat -Skripte auf Codecanyon12 Beste PHP -Chat -Skripte auf CodecanyonMar 13, 2025 pm 12:08 PM

Möchten Sie den dringlichsten Problemen Ihrer Kunden in Echtzeit und Sofortlösungen anbieten? Mit Live-Chat können Sie Echtzeitgespräche mit Kunden führen und ihre Probleme sofort lösen. Sie ermöglichen es Ihnen, Ihrem Brauch einen schnelleren Service zu bieten

Erklären Sie das Konzept der späten statischen Bindung in PHP.Erklären Sie das Konzept der späten statischen Bindung in PHP.Mar 21, 2025 pm 01:33 PM

In Artikel wird die in PHP 5.3 eingeführte LSB -Bindung (LSB) erörtert, die die Laufzeitauflösung der statischen Methode ermöglicht, um eine flexiblere Vererbung zu erfordern. Die praktischen Anwendungen und potenziellen Perfo von LSB

Anpassung/Erweiterung von Frameworks: So fügen Sie benutzerdefinierte Funktionen hinzu.Anpassung/Erweiterung von Frameworks: So fügen Sie benutzerdefinierte Funktionen hinzu.Mar 28, 2025 pm 05:12 PM

In dem Artikel werden Frameworks hinzugefügt, das sich auf das Verständnis der Architektur, das Identifizieren von Erweiterungspunkten und Best Practices für die Integration und Debuggierung hinzufügen.

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heiße Werkzeuge

SublimeText3 Englische Version

SublimeText3 Englische Version

Empfohlen: Win-Version, unterstützt Code-Eingabeaufforderungen!

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Herunterladen der Mac-Version des Atom-Editors

Herunterladen der Mac-Version des Atom-Editors

Der beliebteste Open-Source-Editor

MinGW – Minimalistisches GNU für Windows

MinGW – Minimalistisches GNU für Windows

Dieses Projekt wird derzeit auf osdn.net/projects/mingw migriert. Sie können uns dort weiterhin folgen. MinGW: Eine native Windows-Portierung der GNU Compiler Collection (GCC), frei verteilbare Importbibliotheken und Header-Dateien zum Erstellen nativer Windows-Anwendungen, einschließlich Erweiterungen der MSVC-Laufzeit zur Unterstützung der C99-Funktionalität. Die gesamte MinGW-Software kann auf 64-Bit-Windows-Plattformen ausgeführt werden.

Dreamweaver Mac

Dreamweaver Mac

Visuelle Webentwicklungstools