3

我们有n 个玩家，每个玩家有 3 个值，分别分配给A、B 和 C。

如果存在另一个具有所有 3 个值 A[j] > A[i]、B[j] > B[i] 和 C[j] > C[i] 的玩家j ，则玩家i无法获胜。我们被要求找出无法获胜的玩家数量。

我使用蛮力尝试了这个问题，这是对玩家数组的线性搜索。但它显示TLE。

对于每个玩家i，我正在遍历完整数组以查找是否存在满足上述条件的任何其他玩家j 。

代码 ：

int count_players_cannot_win(vector<vector<int>> values) {
    int c = 0;
    int n = values.size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j!= i && j < n; j++) {
            if(values[i][0] < values[j][0] && values[i][1] < values[j][1] && values[i][2] < values[j][2]) { 
                c += 1;
                break;
           }
        }    
    }
    return c;
}

这种方法是O(n^2)，对于我们遍历完整数组的每个玩家。因此它给出了 TLE。

示例测试用例：

Sample Input

3(number of players)
A B C
1 4 2
4 3 2
2 5 3

Sample Output :

1 

Explanation :
Only player1 cannot win as there exists player3 whose all 3 values(A, B and C) are greater than that of player1.

禁忌：

n(number of players) <= 10^5

解决这个问题的最佳方法是什么？

解决方案：

int n;
const int N = 4e5 + 1;
int tree[N];

int get_max(int i, int l, int r, int L) {  // range query of max in range v[B+1: n]
    if(r < L || n <= l)
        return numeric_limits<int>::min();
    else if(L <= l)
        return tree[i];
    int m = (l + r)/2;
    return max(get_max(2*i+1, l, m, L), get_max(2*i+2, m+1, r, L));
}
void update(int i, int l, int r, int on, int v) { // point update in tree[on]
    if(r < on || on < l) 
        return;
    else if(l == r) {
        tree[i] = max(tree[i], v);
        return;
    }
    int m = (l + r)/2;
    update(2*i+1, l, m, on, v);
    update(2*i+2, m + 1, r, on, v);
    tree[i] = max(tree[2*i+1], tree[2*i+2]);
}

bool comp(vector<int> a, vector<int> b) {
    return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];  
}

int solve(vector<vector<int>> &v) {
    n = v.size();
    vector<int> b(n, 0);           // reduce the scale of range from [0,10^9] to [0,10^5]
    for(int i = 0; i < n; i++) {
        b[i] = v[i][1];
    }
    for(int i = 0; i < n; i++) {
        cin >> v[i][2];
    }

//     sort on 0th col in reverse order
    sort(v.begin(), v.end(), comp);
    sort(b.begin(), b.end());
    
    int ans = 0;
    for(int i = 0; i < n;) {
        int j = i;
        while(j < n &&  v[j][0] == v[i][0]) {    
            int B = v[j][1];
            int pos = lower_bound(b.begin(), b.end(), B) - b.begin(); // position of B in b[]
            int mx = get_max(0, 0, n - 1, pos + 1);
            if(mx > v[j][2])
                ans += 1;
            j++;
        }
        while(i < j) {
            int B = v[i][1];
            int C = v[i][2];
            int pos = lower_bound(b.begin(), b.end(), B) - b.begin(); // position of B in b[]
            update(0, 0, n - 1, pos, C);
            i++;
        }
    }
    return ans;
}

该解决方案使用线段树，从而解决了时间O(n*log(n))和空间O(n)的问题。

@Primusa在接受的答案中解释了方法。

4

1 回答 1

3

首先让我们假设我们的输入以元组列表的形式出现T = [(A[0], B[0], C[0]), (A[1], B[1], C[1]) ... (A[N - 1], B[N - 1], C[N - 1])]

我们可以做的第一个观察是我们可以排序T[0]（以相反的顺序）。然后对于每个 tuple (a, b, c)，为了确定它是否不能获胜，我们询问我们是否已经看到过(d, e, f)这样的 tuple e > b && f > c。我们不需要检查第一个元素，因为给定d > a* 因为T是反向排序的。

好的，那么现在我们如何检查第二个标准？

我们可以像这样重新构建它：在(d, e, f)我们已经看到的所有元组中，e > b最大值是f多少？如果最大值大于c，那么我们知道这个元组不能获胜。

为了处理这部分，我们可以使用具有最大更新和最大范围查询的段树。当我们遇到一个元组(d, e, f)时，我们可以设置tree[e] = max(tree[e], f)。tree[i]将i作为第二个元素表示第三个元素。

要回答“这样的最大值是多少”这样的查询f，e > b我们会max(tree[b+1...])在可能的第二个元素范围内获取最大的第三个元素。

由于我们只进行后缀查询，因此您可以使用修改后的 fenwick 树，但使用段树更容易解释。

这将为我们提供一个解决方案，用于对每个元组O(NlogN)进行排序T和处理我们的段树。O(logN)

*注意：这实际上应该是d >= a. 然而，当我们假装一切都是独一无二的时，更容易解释算法。您需要进行的唯一修改以容纳第一个元素的重复值是在相同值的元组存储桶中处理您的查询和更新。这意味着我们将对具有相同第一个元素的所有元组执行检查，然后我们才更新tree[e] = max(tree[e], f) 所有执行检查的元组。这确保了当另一个元组正在查询树时，没有具有相同第一个值的元组已经更新了树。

于 2020-11-29T06:28:22.160 回答