package realpbms.simulate;

import java.util.Scanner;

/**
 * 很简单的模拟，但是直接字符串输出超时
 * 用stringbuilder处理不会超时
 */
public class P1587 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] hash = new int[111];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = a[i] - 1; j >= 40; j--) {
                res[i] += hash[j];
            }
            hash[a[i]]++;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if(i == n-1){
                sb.append(res[i]);
            }else {
                sb.append(res[i]).append(" ");
            }
        }
        System.out.println(sb);
    }
}

题解描述

在这道题中，需要计算每个小朋友右侧比自己身高低的人的数量。这是一个典型的数组统计问题，可以通过暴力统计方法解决。

代码思路

暴力统计法的核心思想是：

1. 从右到左遍历每一个小朋友，使用一个数组 cnt 来记录当前所有出现过的不同高度小朋友的数量。
2. 每当遍历到一个新的小朋友时，通过数组 cnt 中的数据可以快速计算出比当前小朋友低的所有小朋友的数量。
3. 由于小朋友的身高范围有限（40到110），因此我们可以利用一个定长的数组来存储每个身高出现的频次，从而避免复杂的数据结构并提升性能。

具体步骤如下：

1. 输入数据：首先读取小朋友的数量 n，然后读取每个小朋友的身高并存储在数组 a 中。
2. 遍历并统计：从右向左遍历小朋友，记录当前小朋友的高度，将此高度计数加1，然后在计数数组 cnt 中统计出比当前小朋友低的所有身高的人数总和。
3. 输出结果：结果存储在数组 ans 中，最后依次输出 ans 数组内容。

时间复杂度

对于每个小朋友，统计比自己低的高度的操作在高度范围内（40到110，即70种不同的身高）循环一次。因此时间复杂度为 (O(n \times h))，其中 (h) 为可能的身高值数量，即常数 70。所以，整体复杂度约为 (O(n))，性能可以满足要求。

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];        // 每个小朋友的高度
int cnt[200];    // 每个高度的小朋友个数
int ans[N];      // 最后答案
int n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];        // 输入每个小朋友的高度
    }
    
    // 从右向左遍历所有小朋友
    for(int i = n; i > 0; i--) {        
        cnt[a[i]]++;        // 更新当前小朋友高度的计数
        for(int j = 40; j < a[i]; j++) {
            ans[i] += cnt[j];        // 累加比当前小朋友低的所有小朋友个数
        }
    }
    
    // 输出最终结果
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];  // 输出结果，并避免行末空格
    }
}

Python代码

# 输入数据
n = int(input())
a = list(map(int, input().split()))

# 初始化每个身高小朋友的计数和结果数组
cnt = [0] * 200
ans = [0] * n

# 从右向左遍历
for i in range(n - 1, -1, -1):
    cnt[a[i]] += 1  # 更新当前小朋友的身高计数
    # 统计比当前小朋友身高低的数量
    ans[i] = sum(cnt[j] for j in range(40, a[i]))

# 输出结果
print(" ".join(map(str, ans)))

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        int[] a = new int[n + 1];  // 存储每个小朋友的身高
        int[] cnt = new int[200];  // 记录每个高度的出现次数
        int[] ans = new int[n + 1]; // 存储每个小朋友的报数结果

        // 输入每个小朋友的身高
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        // 从右向左遍历小朋友
        for (int i = n; i > 0; i--) {
            cnt[a[i]]++;  // 更新当前小朋友身高的计数
            // 计算比当前小朋友低的身高数量
            for (int j = 40; j < a[i]; j++) {
                ans[i] += cnt[j];
            }
        }

        // 输出报数结果
        for (int i = 1; i <= n; i++) {
            System.out.print(ans[i] + (i == n ? "\n" : " "));
        }

        scanner.close();
    }
}

说明

1. 数组 cnt：用于记录每种身高出现的频次，从而可以直接查询到比当前身高小的所有小朋友的数量。
2. 遍历顺序：从右向左遍历，以便在统计过程中能够依次更新右侧的身高信息。
3. 高度范围处理：身高的最小值是 40，因此在循环统计低于当前身高的小朋友数量时从 40 开始。这里假设高度的上限不会超过 200，从而将 cnt 定义为长度 200。

这种方法利用身高范围的限制和哈希表统计，从而使复杂度控制在 (O(n)) 左右，可以应对较大的数据输入。