Recherche du maximum de l'élément différence + pour un tableau

Question

Nous avons un tableau composé de chaque entrée sous la forme d'un tuple de deux nombres entiers. Laissez le tableau être A = [(a1, b1), (a2, b2), .... , (an, bn)]. Maintenant, nous avons plusieurs requêtes où nous avons donné un nombre entier x, nous devons trouver la valeur maximale de ai + |x - bi| for 1 <= i <= n.

Je comprends que cela peut être facilement réalisé en O(n) complexité de temps pour chaque requête, mais je cherche quelque chose de plus rapide que cela, probablement O(log n) pour chaque requête. Je peux pré-traiter le tableau en O(n), mais les requêtes doivent être effectuées plus rapidement que O(n).

Toute sorte d'aide serait appréciée.

Answer 1

Il semble être trop facile de trop penser cela.
n = 1 Pour , la fonction est en forme de V avec un minimum de a1 à b1, avec des pentes de -1 et 1, respectivement - que nous appellerons ces valeurs ac et bc (pour combinés).
Pour une paire supplémentaire (ai, bi), l'une des paires peut dominer l'autre (|bc - bi| ≤ |ac - ai), qui peut alors être ignorée.
Sinon, la pente descendante de la combinaison sera de la paire avec la plus grande b, la pente ascendante de l'autre.
Le minimum sera entre l'individu b, plus proche de la b de la paire avec le plus grand a, la distance étant la moitié de la différence entre la (valeur absolue) des différences "coordonnées", la valeur minimale de ce montant plus élevé.
La capture principale est que ni doit être un nombre entier - la seule alternative étant exactement au milieu entre deux nombres entiers.
(. De se retrouver avec la pente descendante de max ai + bi, et la pente montante de max ai - bi)