题解描述

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

代码思路

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

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)) 左右，可以应对较大的数据输入。

题目内容

小明是一位幼儿园院长，他是一位富有经验和激情的教育专业人士。他对幼儿教育充满热情，致力于为幼儿提供最佳的教育和关爱。

作为幼儿园院长，小明在幼儿园的管理和运营方面有着丰富的经验。他深刻理解幼儿的成长和发展需要，关注每一个幼儿的个性和特点，并积极引导他们在安全、温馨、富有启发性的学习环境中成长。

今年春季，小明幼儿园开课了。开春小朋友入学报名参加互联网各大厂的春招。小朋友都排好队。但小朋友的身高有高有低，所以塔老师让所有小朋友报数：以自身为基准向队尾看，有几个比自己矮的小朋友就报几

换句话说：给定整数数组 $nums$ 即为排队的小朋友，要求返回新的数组 $counts$ , $counts[i]$ 为小朋友的报数

输入描述

第一行是数组长度 $N$

第二行是幼儿园小朋友的队列，一个长度 $N$ 的整型数组

$1 \leq nums.length \leq 10^5$ , $40 \leq nums[i] \leq 110$

$counts.length = nums.length$

输出描述

新的整型数组，数组元素是输入中对应位置小朋友的报数

样例

输入

5
81 82 76 75 100

输出

2 2 1 0 0

样例解释：

$81$ 的右侧有2个更小的元素$(76,75)$

$82$ 的右侧有2个更小的元素$(76,75)$

$76$ 的右侧仅有1个更小的元素$(75)$

$75$ 的右侧没有更小的元素

$100$ 的也右侧没有更小的元素