Zählen von Robot-Container-Stacking-Vorgängen in C++ [geschlossen] ⇐ C++

[Anonymous]

Ich versuche ein Problem zu lösen, bei dem ein Roboter Container in einem Lager stapelt, und ich möchte die Anzahl der von ihm ausgeführten Vorgänge berechnen. Die Regeln lauten:

• Es gibt N Container, die in einer einzigen Reihe angeordnet sind.
• Jeder Container hat eine Größe Ai (1 ≤ Ai ≤ M).
• Der Roboter kann einen Container auswählen und ihn in einen größeren Container rechts davon platzieren.
• Ein Container, der bereits einen anderen enthält, kann nicht erneut verwendet werden.
• Ich muss die Gesamtzahl der Roboteroperationen (Verschachtelungen) zählen.

Eingabe:

• Erste Zeile: zwei Ganzzahlen M (maximale Containergröße) und N (Anzahl der Container) />Beispieleingabe:

  Code: Select all

  5 10
  2 2 1 4 3 2 5 4 2 3
  

  Beispielausgabe:

  Code: Select all

  4
  

  Erklärung:
  
  Der Roboter schachtelt Container in den ersten verfügbaren größeren Container rechts von ihm.
• Nachdem 4 Schachtelungen durchgeführt wurden, können keine weiteren Container mehr geschachtelt werden.

Was ich versucht habe:
Ich habe versucht, einen Vektor mit Upper_bound und Lower_bound in umgekehrter Reihenfolge zu verwenden:

Code: Select all

for(auto it = arr.rbegin(); it != arr.rend();it++){
int val = *it;
auto idx = std::upper_bound(S.begin(), S.end(), val);
if (idx != S.end()) {
ops++;
S.erase(idx);
} else {
S.insert(std::lower_bound(S.begin(), S.end(), val), val);
}
}

Es funktioniert für kleine Beispiele, aber ich bin mir nicht sicher, ob es für große N effizient genug ist. Ich habe auch gelesen, dass die Verwendung eines Multisets möglicherweise besser ist. Mit dieser Lösung erreiche ich derzeit 5/100.
Frage:

• Ist dieser Ansatz korrekt und effizient?
• Wie lässt sich dies am besten in C++ implementieren, um N bis zu 20.000 und M bis zu 1.000 zu verarbeiten?