月考成绩

[题目链接](https://www.nowcoder.com/practice/a607d73208a043a6ab73aecb1c49e63a)

思路

每位同学有语文、数学、英语三科成绩。如果存在另一位同学总分比自己高，但至少有一科成绩比自己低，则该同学会产生优越感。求有多少同学会产生优越感。

条件转化

对同学 $i$ ，优越感条件为：存在同学 $j$ ，满足 $\text{tot}_j > \text{tot}_i$ 且 ( $c_j < c_i$ 或 $m_j < m_i$ 或 $e_j < e_i$ )。

取反来看，同学 $i$ 不会产生优越感，当且仅当：

没有任何同学总分比自己高，或者
所有总分比自己高的同学，三科成绩都分别 $\geq$ 自己。

条件 2 等价于：总分严格高于 $\text{tot}_i$ 的所有同学中，语文最小值 $\geq c_i$ ，数学最小值 $\geq m_i$ ，英语最小值 $\geq e_i$ 。

排序 + 维护前缀最小值

按总分从高到低排序，维护已遍历（总分更高）同学的三科最小值 $\text{minC}, \text{minM}, \text{minE}$ 。

对当前同学 $i$ ，若存在总分更高的同学（即不是总分最高的一组），且 $\text{minC} < c_i$ 或 $\text{minM} < m_i$ 或 $\text{minE} < e_i$ ，则该同学产生优越感。

注意：总分相同的同学需要作为一组处理。先用之前（严格更高总分）的最小值判断这一组内所有同学，再将这一组的数据更新到最小值中。

样例演示

输入：

4
100 20 10   → 总分130
100 50 30   → 总分180
20 20 20    → 总分60
60 60 60    → 总分180

按总分降序排列：同学2(180)、同学4(180)、同学1(130)、同学3(60)。

同学2和同学4总分最高（同组），无人比他们更高，不产生优越感。更新 minC=60, minM=50, minE=30。
同学1(100,20,10)：minC=60 < 100，产生优越感。更新 minC=60, minM=20, minE=10。
同学3(20,20,20)：minM=20 不 < 20，minC=60 不 < 20，minE=10 < 20，产生优越感。

答案为 2。

复杂度分析

时间复杂度： $O(n \log n)$ ，排序主导。
空间复杂度： $O(n)$ ，存储成绩和索引。

代码

C++
Java
Python3
JavaScript

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> c(n), m(n), e(n), tot(n);
    vector<int> idx(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i] >> m[i] >> e[i];
        tot[i] = c[i] + m[i] + e[i];
        idx[i] = i;
    }
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return tot[a] > tot[b];
    });
    int ans = 0;
    int minC = INT_MAX, minM = INT_MAX, minE = INT_MAX;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && tot[idx[j]] == tot[idx[i]]) j++;
        for (int k = i; k < j; k++) {
            int id = idx[k];
            if (i > 0 && (minC < c[id] || minM < m[id] || minE < e[id])) {
                ans++;
            }
        }
        for (int k = i; k < j; k++) {
            int id = idx[k];
            minC = min(minC, c[id]);
            minM = min(minM, m[id]);
            minE = min(minE, e[id]);
        }
        i = j;
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] c = new int[n], m = new int[n], e = new int[n], tot = new int[n];
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            c[i] = Integer.parseInt(st.nextToken());
            m[i] = Integer.parseInt(st.nextToken());
            e[i] = Integer.parseInt(st.nextToken());
            tot[i] = c[i] + m[i] + e[i];
            idx[i] = i;
        }
        Arrays.sort(idx, (a, b) -> tot[b] - tot[a]);
        int ans = 0;
        int minC = Integer.MAX_VALUE, minM = Integer.MAX_VALUE, minE = Integer.MAX_VALUE;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && tot[idx[j]] == tot[idx[i]]) j++;
            for (int k = i; k < j; k++) {
                int id = idx[k];
                if (i > 0 && (minC < c[id] || minM < m[id] || minE < e[id])) {
                    ans++;
                }
            }
            for (int k = i; k < j; k++) {
                int id = idx[k];
                minC = Math.min(minC, c[id]);
                minM = Math.min(minM, m[id]);
                minE = Math.min(minE, e[id]);
            }
            i = j;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
students = []
for i in range(n):
    c, m, e = map(int, input().split())
    students.append((c + m + e, c, m, e))

students.sort(key=lambda x: -x[0])

ans = 0
minC = minM = minE = float('inf')
i = 0
while i < n:
    j = i
    while j < n and students[j][0] == students[i][0]:
        j += 1
    for k in range(i, j):
        _, c, m, e = students[k]
        if i > 0 and (minC < c or minM < m or minE < e):
            ans += 1
    for k in range(i, j):
        _, c, m, e = students[k]
        minC = min(minC, c)
        minM = min(minM, m)
        minE = min(minE, e)
    i = j

print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const students = [];
    for (let i = 1; i <= n; i++) {
        const [c, m, e] = lines[i].split(' ').map(Number);
        students.push([c + m + e, c, m, e]);
    }
    students.sort((a, b) => b[0] - a[0]);
    let ans = 0;
    let minC = Infinity, minM = Infinity, minE = Infinity;
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && students[j][0] === students[i][0]) j++;
        for (let k = i; k < j; k++) {
            const [, c, m, e] = students[k];
            if (i > 0 && (minC < c || minM < m || minE < e)) {
                ans++;
            }
        }
        for (let k = i; k < j; k++) {
            const [, c, m, e] = students[k];
            minC = Math.min(minC, c);
            minM = Math.min(minM, m);
            minE = Math.min(minE, e);
        }
        i = j;
    }
    console.log(ans);
});