Ich habe ein Array a[n]
. Die Nummer n
wird von uns eingegeben. Ich muss das Minimalprodukt von finden a[i]
und a[j]
wenn:
1) abs(i - j) > k
2) a[i] * a[j]
wird minimiert
Hier ist meine Lösung (sehr naiv):
#include <iostream>
using namespace std;
#define ll long long
int main() {
ll n,k; cin >> n >> k;
ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];
ll mn; bool first = true;
for(ll i=0;i<n;i++) {
for(ll j=0;j<n;j++) {
if(i!=j)
if(abs(i-j) > k) {
if(first) {
mn = a[i]*a[j];
first = false;
} else if(a[i]*a[j] < mn) mn = a[i]*a[j];
}
}
}
cout << mn << endl;
}
Aber ich möchte wissen, ob es einen schnelleren Weg gibt, ein minimales Produkt mit Abstand zu finden?
c++
algorithm
optimization
minimum
Mouvre
quelle
quelle
std::vector
? @Scheff - Sortieren würde die ursprünglichen "Distanz" -Beziehungen zerstören.if (i!=j) if (abs(i - j) > k)
entfallen. Starten Sie einfach die innere Schleife bei i + k + 1 :for (ll j = i + k + 1; j < n; ++j)
. Die Prüfung mitfirst
kann ebenfalls beseitigt werden, wenn siemn
zuvor zmn = a[0] * a[k + 1];
. B. mit initialisiert wurde . (Vielleichtk
sollte zunächst geprüft werdenn
, ob dies kugelsicher ist.) Aber es ist immer noch O (N²). Das muss schneller machbar sein ...Antworten:
Unter der Annahme, dass mindestens ein Elementpaar die Bedingungen erfüllt und keine Multiplikation von zwei Elementen darin überläuft, kann dies im schlimmsten und besten Fall
Theta(n-k)
zeitlich undTheta(1)
räumlich erfolgen.Dies ist hinsichtlich der asymptotischen Worst-Case-Komplexität sowohl für die Zeit als auch für den Raum optimal, da das optimale Produkt mindestens
a[0]
mit einem dern-(k+1)
Elemente in der Entfernung vorliegen kannk+1
, sodass mindestensn-(k+1)
ganze Zahlen von jedem Algorithmus gelesen werden müssen, der das Problem löst.Die Idee hinter dem Algorithmus ist wie folgt:
Das optimale Produkt verwendet zwei Elemente von
a
, vorausgesetzt, diese sinda[r]
unda[s]
. Ohne Verlust der Allgemeinheit können wir davon ausgehen, dasss > r
das Produkt kommutativ ist.Aufgrund der Einschränkung
abs(s-r) > k
impliziert dies, dasss >= k+1
. Nuns
könnte jeder der Indizes diese Bedingung erfüllen, also iterieren wir über diese Indizes. Dies ist die Iterationi
im angezeigten Code, die jedoch der Einfachheit halber verschoben wirdk+1
(spielt keine Rolle). Für jede Iteration müssen wir das optimale Produkt miti+k+1
dem größten Index finden und es mit der vorherigen besten Schätzung vergleichen.Die möglichen Indizes,
i+k+1
mit denen gepaart werden kann, sindi
aufgrund der Abstandsanforderung alle Indizes kleiner oder gleich . Wir müssten auch alle diese Punkte durchlaufen, aber das ist unnötig, da das Minimum vona[i+k+1]*a[j]
Overj
bei Fixi
gleichmin(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))
der Monotonie des Produkts entspricht (wobei das Minimum sowohl in Bezug auf das Minimum als auch das Maximuma[j]
für die beiden möglichen berücksichtigt wird Zeichena[i+k+1]
oder gleichwertig die beiden möglichen Richtungen der Monotonie.)Da die Menge der
a[j]
Werte, über die wir hier optimieren, gerade ist{a[0], ..., a[i]}
und die einfach um ein Element (a[i]
) in jeder Iteration von wächsti
, können wir einfachmax(a[j])
undmin(a[j])
mit einzelnen Variablen verfolgen , indem wir sie aktualisieren, wenn siea[i]
größer oder kleiner als die vorherigen optimalen Werte sind. Dies erfolgt mitback_max
undback_min
im Codebeispiel.Der erste Schritt der Iteration (
i=0
) wird in der Schleife übersprungen und stattdessen als Initialisierung der Variablen ausgeführt.quelle
a[i+k+1]
dem Minimum und Maximum sind.Ich bin mir nicht sicher, ob ich am schnellsten bin .
Für das einfachere Problem ohne i <j - k gehört das Minimalprodukt zu den Produkten von Paaren aus den beiden kleinsten und größten Elementen.
Also (das Folgende ist zu kompliziert, siehe Walnuss-Antwort )
(• Hindernis, wenn k ≤ n
• min initialisiereProdukt auf a [0] * a [k + 1])
beginnend mit {} und {a [ j ] | k ≤ j }
min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
max ( upToI ) × min ( beyondIplusK ) und max ( upToI ) × max ( beyondIplusK ).
quelle
minUpto
,maxUpto
,minBeyond
,maxBeyond
(Sie in zwei Iterationen erstellen können)? Finden Sie dann in der dritten Iteration für jeden Index die minimal mögliche Multiplikation.Für "minimale Größe"
Suchen Sie die 2 Elemente "kleinster Größe" und multiplizieren Sie sie (nachdem Sie entweder zwei Nullen gefunden oder das gesamte Array durchsucht haben).
Für "niedrigsten Wert" ohne das
abs(i - j) > k
TeilEs gibt 3 Möglichkeiten:
die zwei höchsten (kleinste Größe) negativen Zahlen
die zwei niedrigsten (kleinste Größe) nicht negativen Zahlen
die niedrigste (größte Größe) negative Zahl und die höchste (größte Größe) nicht negative Zahl
Sie könnten nach allen 6 Werten suchen und die Produkte herausfinden, die am Ende am besten sind.
Jedoch; Sobald Sie eine Null sehen, wissen Sie, dass Sie nicht mehr über die ersten beiden Möglichkeiten Bescheid wissen müssen. und sobald Sie eine negative und eine nicht negative Zahl sehen, wissen Sie, dass Sie sich nur um die dritte Möglichkeit kümmern.
Dies führt zu einer endlichen Zustandsmaschine mit 3 Zuständen - "Sorge um alle 3 Möglichkeiten", "Antwort ist Null, es sei denn, eine negative Zahl wird gesehen" und "Sorge nur um die letzte Möglichkeit". Dies kann als ein Satz von 3 Schleifen implementiert werden, wobei 2 der Schleifen in (
goto
) die Mitte einer anderen Schleife springen, wenn sich der Zustand (der endlichen Zustandsmaschine) ändert.Insbesondere könnte es etwas vage aussehen (ungetestet):
Für "niedrigsten Wert" mit dem
abs(i - j) > k
TeilIn diesem Fall haben Sie noch die 3 Möglichkeiten; und könnte dazu führen, dass es mit dem gleichen Ansatz "3 Schleifen mit endlicher Zustandsmaschine" funktioniert, aber es wird zu chaotisch / hässlich. In diesem Fall ist es wahrscheinlich, dass eine bessere Alternative das Array vorab scannt, um festzustellen, ob Nullen vorhanden sind und ob alle negativ oder alle positiv sind. Damit Sie nach dem Pre-Scan entweder wissen, dass die Antwort Null ist, oder eine Schleife auswählen können, die nur für die jeweilige Möglichkeit ausgelegt ist.
quelle