Algorithm to find weighted ranking?-CodePudding

I want to find the rank of a person based on different parameters and each parameter has different weights assigned to them.

For e.g. Suppose if there are three items a, b and c, these items could have any value between 0 to 10,00,000. There are weights assigned to them a = 0.3 , b=0.2, c=0.1. Suppose there are 10,000 people have these items with different quantity. Suppose a person X have items a=2200, b = 4000, c= 1280. Then how could I find the rank of person x within 10,000 people that where he lies.

Please let me know if needs more details.

Immediate help appreciated.

CodePudding user response：

First, calculate the weighted points of all persons. That is,

P[i] = Wa * a[i]   Wb * b[i]   Wc * c[i];

Then sort all P[i] by its values.

You can define and use the custom compare function to get rank easily.

    for (int i = 0; i < n; i  ) rank[i] = i;
    sort (rank, rank   n, [P](int i, int j) {
        return P[i] < P[j];
    });

In case of dynamic insert and get rank operation, you have to use order-statistics tree. Then you can get the performance result of O(logn) for both operations.

Please refer codeforces and this article for more details.