我的答案：北大ACM#1007（DNA Sorting）
好久没做 ACM 了，昨晚又跑到北大的上面做了一题（没敢去浙大的，ZOJ 的判定比北大严格得多），题目就不抄了，自己去看吧， 1007 - DNA Sorting。
下面我把自己的答案贴出来，说实话我这个代码非常烂，虽然 Accepted，但占用内存 300K，耗时 375 MS，代码长度 2261B，跟排在前面的高手的解决方法完全不能比——第 1 名：占用内存 4K，耗时 0 MS，代码长度 847B……第 20 名，占用内存 12K，耗时 0 MS，代码长度 554B——可能是我写的代码太过于 C++ 了，不仅有类，还用了模板，相当依赖 STL。如果有高手看到我这个帖子，希望能多多指教。
#include <iostream>
#include <string>
#include <vector>
class MySequence
{
public:
explicit MySequence(std::string strSequence)
{
_strSequence = strSequence;
_nUnsortedness = 0;
};
MySequence(void)
: _strSequence()
, _nUnsortedness(0)
{
};
~MySequence(void) {};
public:
int getUnsortedness()
{
_nUnsortedness = 0;
int nStrLength = _strSequence.length();
for (int i = 0; i <nStrLength; i++)
{
// strSequence[i] stands for every letter
for (int j = i+1; j <nStrLength; j++)
{
if (_strSequence[i]> _strSequence[j])
_nUnsortedness++;
}
}
return _nUnsortedness;
};
inline std::string getSequence()
{
return _strSequence;
};
private:
std::string _strSequence;
int _nUnsortedness;
};
std::vector<MySequence> vecSequenceList;
void setInput()
{
int nSequenceLength = 0, nVectorSize = 0, nIndex = 0;
std::string strInput;
std::cin>> nSequenceLength>> nVectorSize;
while (nIndex <nVectorSize)
{
std::cin>> strInput;
MySequence msSequence(strInput);
vecSequenceList.push_back(msSequence);
nIndex++;
}
}
int main(int argc, char* argv[])
{
// 输入序列
//
setInput();
// 计算序列的逆序数并按规则排序
//
MySequence msTemp;
for (int i = 0; i <vecSequenceList.size(); i++)
{
for (int j = 0; j <vecSequenceList.size()-i-1; j++)
{
if (vecSequenceList[j].getUnsortedness()> vecSequenceList[j+1].getUnsortedness())
{
msTemp = vecSequenceList[j];
vecSequenceList[j] = vecSequenceList[j+1];
vecSequenceList[j+1] = msTemp;
}
}
}
// 输出序列
//
for (int i = 0; i <vecSequenceList.size(); i++)
std::cout <<vecSequenceList[i].getSequence() <<std::endl;
return 0;
}
POKING 2008年04月19日 20:05 ₪
死机啊，好久没登你的网站，见识不少东西，看到你的最新著作，我来评几句啊，下面是纯属我个人的观点。
1：冒泡法的效率比较低，可以尝试适合具体情况的排序算法。
2:排序的时候，你每次调用getUnsortedness()是不划算的做法（而且你这里又是个复杂度为O(n平方)的一个算法，就显得更不划算了），不如在构造还属里直接运行getUnsortedness()，然后记录这个值,作为属性直接访问，vc里好像应为public variables或使用inline函数，就像你的
inline std::string getSequence()
{
return _strSequence;
};
3： Class是耗费了大量内存，没有必要把每个字符串作为一个对象来处理（针对这个题目），创建一个Class也要耗费一定的时间和大量内存。
4：没有必要使用模板。既然size是已知的(nVectorSize))为什么又要vector::Size()。
北极冰仔 2008年04月20日 10:49 ₪
@POKING 谢谢小泡指点，确实如你所说，在这些地方我都没有仔细考虑开销的问题，我想这就是造成程序效率低下的根本原因。我会尝试针对这些问题做些改进。哈哈，最后还是谢谢小泡！祝你出差愉快！
POKING 2008年04月20日 16:14 ₪
称不上指点啦，切磋切磋。你的博客比较好玩！
小猪有什么要帮忙的，帮忙多照顾照顾啊。
北极冰仔 2008年04月21日 17:56 ₪
@POKING 呵呵，放心啦！
Jiang 2008年04月22日 07:34 ₪
我的一点个人看法：
由于DNA strings仅含有ACGT四个字母，因此如果做针对性处理，getUnsortedness算法可以从O(n平方)提高到O(n)。下面是一个getunsortness的例子。
typedef struct A
{
int c;
}A;
typedef struct C
{
int c;
int ac;
}C;
typedef struct G
{
int c;
int ac;
int cc;
}G;
typedef struct T
{
int c;
int ac;
int cc;
int gc;
}T;
int UnSort(char* s, int l)
{
int i = 0;
A a={0};
C c={0};
G g={0};
T t={0};
while(i<l)
{
if(s[i]==’A')
a.c++;
else if(s[i]==’C')
{
c.c++;
c.ac+=a.c;
}
else if(s[i]==’G')
{
g.c++;
g.ac+=a.c;
g.cc+=c.c;
}
else
{
t.c++;
t.ac+=a.c;
t.cc+=c.c;
t.gc+=g.c;
}
i++;
}
return a.c*(c.c+g.c+t.c)+c.c*(g.c+t.c)+g.c*t.c-c.ac-g.ac-g.cc-t.ac-t.cc-t.gc;
}
北极冰仔 2008年04月22日 10:49 ₪
@Jiang
狂汗，暂时还没看懂 -__-||
不过有高手现身我还是很高兴！
Train Dolphins 2008年04月22日 14:36 ₪
Nice message.
I think you will check out our page..
Ciao
Ralph Zhang 2008年05月06日 23:37 ₪
C++用的好并不会慢太多，不过交换元素位置用value copy就不敢恭维了
北极冰仔 2008年05月07日 09:48 ₪
@Ralph Zhang 的确有这个问题，有时候感觉自己的思维很差劲，根本没有考虑效率。感谢提醒！