题目描述

有一批服务器需要根据性能评分做分类。每台服务器有计算和存储两个性能评分，如果存在至少一台其他服务器的计算和存储性能评分都严格大于该服务器，则该服务器被标记为老旧服务器。给定服务器的评分，计算其中老旧服务器的数量。

输入描述

• 第一行输入一个整数$n$，表示服务器的数量，$2 \leq n \leq 10^5$。
• 接下来的$n$行，每行包含两个整数$server[0]$和$server[1]$，分别表示服务器的计算性能评分和存储性能评分。
• $1 \leq server[0], server[1] \leq 10^5$。

输出描述
输出一个整数，表示老旧服务器的数量。

解题思路

1. 排序规则

   • 按服务器的计算性能降序排序；如果计算性能相同，则按存储性能升序排序。
   • 排序后，保证遍历时，后面的服务器在计算性能上不可能超过前面的服务器。

2. 统计老旧服务器

   • 使用变量max_storage记录已遍历服务器的最大存储性能。
   • 遍历服务器时，如果当前服务器的存储性能小于max_storage，说明它是老旧服务器；否则，更新max_storage。

3. 时间复杂度

   • 排序耗时$O(n \log n)$，单次遍历耗时$O(n)$，总复杂度为$O(n \log n)$。

代码实现

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 自定义排序函数：计算性能降序，计算性能相同时按存储性能升序
bool compare(const vector<int>& a, const vector<int>& b) {
    if (a[0] == b[0]) {
        return a[1] < b[1];
    }
    return a[0] > b[0];
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> servers(n);

    // 输入服务器评分
    for (int i = 0; i < n; i++) {
        cin >> servers[i][0] >> servers[i][1];
    }

    // 排序
    sort(servers.begin(), servers.end(), compare);

    int old_count = 0;     // 老旧服务器数量
    int max_storage = -1;  // 当前最大存储性能

    // 遍历服务器，统计老旧服务器
    for (int i = 0; i < n; i++) {
        if (servers[i][1] < max_storage) {
            old_count++;  // 如果当前存储性能小于最大值，则为老旧服务器
        } else {
            max_storage = servers[i][1];  // 更新最大存储性能
        }
    }

    cout << old_count << endl;
    return 0;
}

Python 实现

# 输入与排序
n = int(input())
servers = []

for _ in range(n):
    comp, store = map(int, input().split())
    servers.append((comp, store))

# 排序：计算性能降序，计算性能相同时存储性能升序
servers.sort(key=lambda x: (-x[0], x[1]))

old_count = 0  # 老旧服务器数量
max_storage = -1  # 当前最大存储性能

# 遍历服务器，统计老旧服务器
for _, store in servers:
    if store < max_storage:
        old_count += 1  # 如果存储性能小于最大值，则为老旧服务器
    else:
        max_storage = store  # 更新最大存储性能

print(old_count)

Java 实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] servers = new int[n][2];

        // 输入服务器评分
        for (int i = 0; i < n; i++) {
            servers[i][0] = sc.nextInt();
            servers[i][1] = sc.nextInt();
        }

        // 排序：计算性能降序，计算性能相同时存储性能升序
        Arrays.sort(servers, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]); // 存储性能升序
            }
            return Integer.compare(b[0], a[0]); // 计算性能降序
        });

        int oldCount = 0;    // 老旧服务器数量
        int maxStorage = -1; // 当前最大存储性能

        // 遍历服务器，统计老旧服务器
        for (int i = 0; i < n; i++) {
            if (servers[i][1] < maxStorage) {
                oldCount++; // 如果存储性能小于最大值，则为老旧服务器
            } else {
                maxStorage = servers[i][1]; // 更新最大存储性能
            }
        }

        System.out.println(oldCount);
    }
}

题目内容

有一批服务器需要根据性能评分做分类，当前已经针对每一台服务器的计算和存储性能进行打分。给定n 个包含$2$个整数的数组$server[2]$，代表$n$台服务器的评分，其中$server[0]$ 表示服务器的计算性能评分，$server[1]$表示服务器的存储性能评分，对于一台服务器，如果存在至少一台其他服务器的计算和存储性能都大于该服务器，那么该服务器被标记为老旧服务器，请根据给定的$n$台服务器的性能评分，计算出其中老旧服务器的数量。

输入描述

第一行输入一个整数n，表示服务器的数量，$2<=n <=10^5$ 接下来有$n$行输入，每一行为$1$个整数数组$server[2]$，数组元素使用空格分割，$server[0]$、$server[1]$分别表示这台服务器的计算和存储性能评分 $1 <= server[0]，server[1] <=10^5$

输出描述

输出一个整数，表示给定的$n$台服务器中老旧服务器的数量

样例1

输入

3
5 5
6 3 
3 6

输出

0

说明

没有一台服务器的计算和存储性能都小于其他的服务器，因此输出$0$

样例2

输入

3
1 5
10 4
4 3

输出

1 

说明

评分为$4\ 3$的服务器计算和存储性能都小于评分为$10\ 4$的服务器，因此存在$1$台服务器为老旧服务器