排队(line)——2015年南海区青少年信息学奥林匹克竞赛试题(小学甲组)

排队(line)——2015年南海区青少年信息学奥林匹克竞赛试题(小学甲组)

排队(line)

题目描述

楠楠最近在研究南海区5年级英语成绩的排序有关算法，如果数列中的数是从小到大排列的，则称有序的。研究中对于没有排好序的数列，要统计每个数前面有多少比它大的数字。比如有5个数的数列： 3 1 4 2 5，则第1个数3之前有0个数比它大；第2个数1之前有1个数比它大；第3个数4之前有0个数比它大；第4个数2之前有2个数比它大；第5个数5之前有0个数比它大。由于数列很长，楠楠求你编程来统计。 输入格式：
第一行1个整数N，表示数列有N个整数。
第二行有N个非负整数，每个数表示一个分数，范围是[0…120]。 输出格式：
一行N个非负整数(中间有空格)，第i个数表示原数列中第i位前有多少比第i位数大。
输入样例：

5
3 1 4 2 5

输出样例：
0 1 0 2 0
数据范围：

• 8个的数据： N的范围是[1…1000]，每个数范围是[0…120]
• 2个的数据：N的范围是[1…1,00,000]，每个数范围是[0…120]

解题思路

使用归并排序来计算各个位置的逆序数

代码实现

#include <stdio.h&