问题 B: 所有的逆序对

问题 B: 所有的逆序对

时间限制: 2 Sec  内存限制: 5 MB
提交: 1077  解决: 193
提交 状态 算法问答 

题目描述

请大家在做oj题之前,仔细阅读关于抄袭的说明http://www.bigoh.net/JudgeOnline/.


给出一个字符串数组,如果(按照字典序)一个大的字符串在比它小的字符串前面我们称这两个字符串组成一个“逆序对”。你需要找到所有的逆序对的个数。

注:在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即a、b、c……z 的顺序);如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。通过这种方法,我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串。

输入

第一行是数组大小,第二行是以空格分隔的字符串数组.

注:预先知道每个字符串的长度都是 10.

输出

所有的逆序对个数. 这次需要大家先输出一个字符串,它是“我已阅读关于抄袭的说明”的汉语拼音.输出此行的提交我们将认为已经完全阅读并了解了“关于抄袭的说明”公告.

注意:结果比较大,请用 long 类型保存.

样例输入

3
aaaaaaaaaa cccccccccc bbbbbbbbbb

样例输出

wo yi yue du guan yu chao xi de shuo ming
1

提示

不要使用蛮力算法

提交 状态