Obergrenze
Gegeben ist ein Array mit
n sortierten Ganzzahlen. Sie sollen q Anfragen beantworten. Jede Anfrage lautet: „Welches ist die erste Zahl in der Liste, die größer ist als x?“.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
n (2 ≤ n ≤ ) und q (1 ≤ q ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte Ganzzahlen ( ≤ ≤ ) in aufsteigender Reihenfolge.Die letzte Zeile enthält
q durch Leerzeichen getrennte Anfragen ( ≤ < ).Ausgabe
Das Programm soll
q Zeilen ausgeben. In jeder Zeile steht die Antwort auf die jeweilige Anfrage.Beispiele
Eingabe | Ausgabe |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Hinweis
In der klassischen Implementierung der binären Suche betrachten wir den Bereich
[l; r), wobei l eingeschlossen ist und r nicht. Manchmal kann es jedoch sinnvoll sein, (l; r] zu verwenden – also l auszuschließen und r einzuschließen. Dafür müssen Sie beim Berechnen von l, r und mid einige Anpassungen vornehmen.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB