学生人数有更好的成绩和更低的JEE排名 [英] Number of students with better grades and lower jee rank

问题描述

我们正在给定的n学生CGPA（大学成绩）和JEE行列每个学生（等级在招生联考）。 对于每一个学生，我们要计算谁拥有更好的CGPA但糟糕的高考排名的学生人数。

We are given n students with cgpa (college grades) and jee ranks (Rank in admission exam) of every student. For every student, we have to calculate the number of students who have better cgpa but worse jee rank.

（X1，Y1），（X2，Y2）......（十一，彝族）...（XN，YN）

(x1,y1), (x2,y2) ...(xi,yi)... (xn,yn)

对于每个i，我们要计算没有。第j为此XJ> xi和YJ>义（更糟糕的排名意味着更好的排名。）

for each i, we have to calculate no. of j for which xj > xi and yj > yi (worse rank means greater rank.)

我可以用下面的nlogn算法 - 拿出     对它们进行排序下降CGPA。     现在，从左边开始扫描。     保持扫描至今在平衡二叉树（根据自己的高考等级）的学生。     在接下来的学生，只要找到了不已经扫描更大级别的学生通过查询平衡二叉树。

I could come up with the following nlogn algorithm- Sort them decreasing cgpa. Now start scanning from left. Maintain the students scanned so far in a balanced binary tree (according to their jee rank). For the next student, just find out the no of students already scanned with greater rank by querying the balanced binary tree.

我不知道如何保持平衡BST，我可以不返回。在O（LOGN）元素少于k个。我们需要保持无。在子树的每个节点的节点。但如何做到这一点？

I don't know how to maintain a balanced bst in which i can return no. of elements less than k in O(logn). We would need to maintain no. of nodes in subtree at each node. But how to do that?

无论是帮助上述或者提供不同的算法，或许DP。

Either help with the above or else provide a different algorithm, perhaps DP.

推荐答案

如果你不想code平衡二叉树，二进制索引树（又名位或树状数组）是您应该看的DS 。它可以是codeD与＆lt; 10个简单的线条。 这里是一个博客帖子我写的芬威克树木可能会有所帮助。

If you don't want to code balanced binary tree, Binary Indexed Tree (aka BIT or Fenwick Tree) is the DS you should be looking at. It can be coded in < 10 easy lines. Here is a blog post I wrote on Fenwick Trees that might help.

这篇关于学生人数有更好的成绩和更低的JEE排名的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！