第03次上机实验题目（分治策略）#

---

利用分治策略设计算法，编程解决下列问题：

---

一、 众数问题：【问题描述】给定含有S个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1,2,2,2,3,5}。多重数S的众数是2，其重数为3 。#

【算法设计】对于给定的由n个自然数组成的多重集S，计算S的众数及其重数。

输入格式#

第1行为多重数集S中元素个数n；接下来的n行中，每行有一个自然数。

输出格式#

输出文件有2行，第1行是众数，第2行是重数。

样例输入#

6
1
2
2
2
3
5

样例输出#

2
3

---

二、 逆序对计数#

问题描述#

对于给定的数组 $A$，计算其逆序对的总数。即满足以下条件的数对 $(i, j)$ 的总个数：

$$i < j \quad \text{且} \quad A[i] > A[j]$$

输入格式#

输入包含 1 组测试用例。

一个测试用例占一行，第一个整数表示数组的长度 $n$，后面紧跟着数组中的各个整数元素 $A[i]$，中间都用一个空格分开。

• 数组的长度范围：$1 \le n \le 10^5$
• 每个数字 $A[i]$ 的范围：$0 \le A[i] \le 10^9$

输出格式#

输出一个整数，表示逆序对的个数。

样例输入#

5
1 2 3 5 4

样例输出#

1