Warum zeigt meine Rangliste falsche Ränge für gebundene Bewertungen (Python)? ⇐ Python

[Anonymous]

Ich implementiere eine Spiele -Rangliste in Python, in der Spieler die gleiche Punktzahl haben können (Krawatten), und ich muss drei Operationen effizient unterstützen: < /p>

add_score Player_id -Score Aktualisieren Sie die Punktzahl eines Spielers (ignorieren Sie, wenn die neue Punktzahl nicht höher ist. Punktzahl) < /li>
get_score_by_rank Rank - Ret die Punktzahl der Spieler (en) bei einem bestimmten Rang zurück (die Bindungen sollten den gleichen Rang teilen) < /li>
< /ul>
Zum Beispiel sollte diese Sequenz wie folgt funktionieren: < /p>

Code: Select all

> out
1
1
1
1
2
1
2
120
< /code>
Ich verwende einen AVL -Baum, um diese Vorgänge effizient zu unterstützen.115,11253,1875
116,2199,1869
116,11972,1869
118,717,1863
118,3432,1863
121,783,1859
122,11760,1852
< /code>
Aber ich erwarte Ränge wie 118, 118, 120 für gebundene Bewertungen anstelle von 118, 118, 121. Ich bekomme Ausgabe wie 116, 116, 118 für gebundene Scores, was korrekt ist. Ranking- und Krawattenhandling.  /> Aber ich kann nicht genau bestimmen, woher der von Off-by-One-Fehler für gebundene Bewertungen stammt.import sys

class AVLNode:
def __init__(self, score):
self.score = score
self.players = set()
self.count = 0
self.height = 1
self.left = None
self.right = None
self.total = 0

class AVLTree:
def __init__(self):
self.root = None

def _height(self, node):
return node.height if node else 0

def _update(self, node):
if not node:
return
node.height = 1 + max(self._height(node.left), self._height(node.right))
left_total = node.left.total if node.left else 0
right_total = node.right.total if node.right else 0
node.total = left_total + right_total + node.count

def _balance_factor(self, node):
return self._height(node.left) - self._height(node.right)

def _rotate_left(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
self._update(z)
self._update(y)
return y

def _rotate_right(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
self._update(z)
self._update(y)
return y

def _balance(self, node):
if not node:
return node
balance = self._balance_factor(node)
if balance > 1:
if self._balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance < -1:
if self._balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node

def _insert(self, node, score, player_id):
if not node:
new_node = AVLNode(score)
new_node.players.add(player_id)
new_node.count = 1
new_node.total = 1
return new_node

if score > node.score:
node.left = self._insert(node.left, score, player_id)
elif score < node.score:
node.right = self._insert(node.right, score, player_id)
else:
if player_id not in node.players:
node.players.add(player_id)
node.count += 1
node.total += 1
return node

self._update(node)
return self._balance(node)

def _remove(self, node, score, player_id):
if not node:
return None

if score > node.score:
node.left = self._remove(node.left, score, player_id)
elif score < node.score:
node.right = self._remove(node.right, score, player_id)
else:
if player_id in node.players:
node.players.remove(player_id)
node.count -= 1
node.total -= 1
if node.count >  0:
self._update(node)
return self._balance(node)
if not node.left:
return node.right
elif not node.right:
return node.left
temp = self._min_value_node(node.right)
node.score = temp.score
node.players = set(temp.players)
node.count = temp.count
node.right = self._remove(node.right, temp.score, next(iter(temp.players)))
self._update(node)
return self._balance(node)

def _min_value_node(self, node):
current = node
while current.left:
current = current.left
return current

class Leaderboard:
def __init__(self):
self.player_scores = {}
self.tree = AVLTree()

def add_score(self, player_id, new_score):
if player_id in self.player_scores:
old_score = self.player_scores[player_id]
if new_score  current.score:
current = current.left
else:
left_total = current.left.total if current.left else 0
higher_count += left_total
break
return higher_count + 1

def get_score_by_rank(self, rank):
if rank < 1 or not self.tree.root or rank > self.tree.root.total:
return -1
current = self.tree.root
count = 0
while current:
left_total = current.left.total if current.left else 0
if count + left_total >= rank:
current = current.left
elif count + left_total + current.count < rank:
count += left_total + current.count
current = current.right
else:
return current.score
return -1

if __name__ == '__main__':
leaderboard = Leaderboard()
outputs = []
for line in sys.stdin:
line = line.strip()
if not line:
continue
parts = line.split()
cmd = parts[0]
if cmd == 'add_score':
player_id = int(parts[1])
score = int(parts[2])
outputs.append(str(leaderboard.add_score(player_id, score)))
elif cmd == 'get_rank':
player_id = int(parts[1])
outputs.append(str(leaderboard.get_rank(player_id)))
elif cmd == 'get_score_by_rank':
rank = int(parts[1])
outputs.append(str(leaderboard.get_score_by_rank(rank)))
print('\n'.join(outputs))