c++，统计每个数前面有多少比它大的数

Question

给出N个整数，要统计每个数前面有多少比它大的数字。比如有5个数的数列:25134,则第1个数2之前有0个数比它大;第2个数5之前有0个数比它大:第3个数1之前2个数比它大:第4个数3之前有1个数比它大:第5个数4之前有1个数比它大。
数据范围:每个数范围[0..200]，N<=10^5

#include<bits/stdc++.h>
using namespace std; 
int d[100001];
int c[1300];
int main(){
int n, ans,x;
 cin>>n;
for (int i=0; i<n; i++)
cin>>           ;
for (int i=0; i<n; i++){
                  ;
for(int j=_____;j<200;j++)
              ;
 cout<<ans<<” ”;
                     ;
}
cout<<endl;

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

要解决这个问题，我们可以使用一个计数数组来记录每个数字出现的次数。然后遍历这个数组，对于每个数字，我们计算它前面所有比它大的数字的总和。下面是完成的C++代码示例：

#include<bits/stdc++.h>
using namespace std; 

int main(){
    int n, x;
    cin >> n;
    vector<int> count(201, 0); // 计数数组，记录每个数字出现的次数

    // 读取N个整数，并更新计数数组
    for (int i = 0; i < n; i++) {
        cin >> x;
        count[x]++;
    }

    // 计算前面比当前数字大的数字的总数
    int prefixSum = 0; // 前缀和
    for (int i = 0; i < n; i++) {
        cin >> x; // 再次读取数字，因为cin已经读取到了下一个数
        cout << prefixSum << " "; // 输出结果
        prefixSum += count[x] - 1; // 更新前缀和，减1是因为当前数字不计入
        count[x]--;
    }
    cout << endl;
    return 0;
}

这段代码首先读取N个整数，并使用一个计数数组count来记录每个数字出现的次数。然后，它再次遍历输入，这次是为了输出每个数字前面比它大的数字的数量。对于每个数字x，它使用前缀和prefixSum来计算前面比x大的数字的总数，然后输出这个数量，并更新prefixSum。

注意，这段代码假设输入的数字是按照非递减的顺序给出的。如果输入的数字是无序的，我们需要在读取数字后先对它们进行排序，然后再进行上述的统计。

由于问题的数据范围是N<=10^5，这种方法的时间复杂度是O(N)，空间复杂度是O(1)，因为它只使用了一个固定大小的数组来记录计数信息。这应该足够高效，以适应大数据处理的需求。

关于参考链接，由于这是一个相对简单的算法问题，通常不需要外部链接来解决。但是，如果你需要更多关于C++编程或算法的资源，可以考虑以下链接：

• C++ 官方文档
• GeeksforGeeks
• Stack Overflow

这些网站提供了大量的编程教程、算法解释和社区支持，可以帮助你解决更复杂的问题。