我们有n个玩家，每个玩家都有三个值 A，B 和 C。
如果存在另一个玩家 j 满足 A[j] > A[i]，B[j] > B[i]，C[j] > C[i]，那么玩家 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;
}
该解决方案使用线段树(segment tree)，因此以时间复杂度O(n*log(n))和空间复杂度O(n)的方式解决了问题。
方法在接受的答案中由@Primusa解释。