#P1094. 时空隧道的密码

时空隧道的密码

问题描述

小核桃一行人被困在了 时空隧道 之内,现在他们在尝试破解密码。

小核桃知道密码的提示:一个由 0011 字符组成的字符串,密码就是这个字符串的逆序对数。

但是由于故障,这个提示破碎了,变成了 nn 个由 0011 组成的字符串,现在他们需要把这 nn 个字符串自由排列并拼接起来得到原提示和密码。

当然,可能的拼接方案太多了,不过幸运的是,得到了某位的帮助,他们知道提示的逆序对数是所有拼接方案里逆序对数最少的。

但即使这样,这个问题也很难,所以他们希望你能够帮助他们,得到最后的密码。

sis_i 表示字符串 ss 的第 ii 个字符,一个逆序对是指一个点对 (i,j)(i,j) 满足 i<ji<jsi>sjs_i>s_j

输入描述

第一行一个正整数 nn ,表示字符串的个数。

接下来 nn 行每行一个给定的字符串。

输出描述

输出一个整数表示密码,即最少的逆序对数。

3
1
11
101
1
3
1010
111
101
6

样例解释 1

逆序对数最少的字符串为 101111.

数据范围和说明

MM 为所有字符串长度之和。

测试点编号 数据约束
121-2 1n8,1m201\le n\le 8,1\le m\le 20
343-4 1n18,1m301\le n\le 18,1\le m\le 30
585-8 1n18,1m1051\le n\le 18,1\le m\le 10^5
99 1n=M2×1051\le n=M\le 2\times 10^5
101110-11 n=1,1M2×105 n=1, 1\le M\le 2\times 10^5
121512-15 n1000,1m105n\le 1000,1\le m\le 10^5
162016-20 1n2×105,1M2×1051\le n\le 2\times 10^5, 1\le M\le 2\times 10^5

大样例

大样例下载