On nous donne n étudiants avec cgpa (grades collégiaux) et grades jee (classement à l'examen d'admission) de chaque élève. Pour chaque étudiant, nous devons calculer le nombre d'étudiants qui ont un meilleur grade de cgpa mais plus mauvais.Nombre d'élèves ayant de meilleures notes et un plus faible rang de jee
(x1, y1), (x2, y2) ... (xi, yi) ... (xn, yn)
pour chaque i, nous devons calculer pas. de j pour lequel xj> xi et yj> yi (pire rang signifie plus grand rang.)
Je pourrais trouver l'algorithme nlogn suivant - Trier les cgpa décroissantes. Lancez maintenant la numérisation à partir de la gauche. Maintenir les élèves scannés jusqu'ici dans un arbre binaire équilibré (selon leur rang jee). Pour le prochain élève, il suffit de connaître le nombre d'élèves déjà numérisés avec un rang supérieur en interrogeant l'arbre binaire équilibré. Je ne sais pas comment maintenir un bst équilibré dans lequel je peux retourner non. des éléments inférieurs à k dans O (logn). Nous aurions besoin de maintenir non. des noeuds dans le sous-arbre de chaque noeud. Mais comment faire ça?
Soit aider avec ce qui précède ou sinon fournir un algorithme différent, peut-être DP.
Comment avez-vous l'intention de trouver une liste d'étudiants qui ont une meilleure MPC mais des notes moins bonnes? Cela ne me semble pas logique. Comment la MPC peut-elle être inversement proportionnelle au rang? – Ajai
L'AAPC signifie les notes au collège, et le rang se rapporte au rang parmi tous les étudiants qui sont apparus pour le test d'admission de ce collège. Les deux n'ont aucune relation entre eux. –
'Pour l'étudiant suivant, il suffit de rechercher le nombre d'élèves déjà numérisés avec un rang supérieur en interrogeant l'arbre binaire équilibré. Vous ne pouvez pas avoir un même arbre équilibré pour différents attributs. –