题目地址:http://poj.org/problem?id=1007
刚开始想到的这道题大概的思路是:用vector嵌套的map<int,string>来存储输入的每行DNA序列。由于STL中,map<key,value>结构在插入时,可以根据key的值升序插入每行数据,因此考虑这种方法。初步写出如下代码:
其中,calculate()用于计算逆序数,实现也很简单:
但是,测试几组数据之后,发现经常出现缺少DNA序列的情况,设置断点调试之后发现:原来是向map中插入数据时,有些数据没插进去。
原来通过成员函数insert和STL的pair,向map<key,value>结构插入逐条数据时,当key的值之前已经出现过时,插入不成功。需要使用multimap<key,value>进行插入。
修改之后,提交成功。