学步园

这道题还是比较简单的，c++中的类特别好用，如果拿C写的话，自己得编好多代码，当然效率应该会更高些，不过从memory:260k, time:oMs来看，只是内存消耗大些。这里主要使用了multimap<int,string>这个类。用unsortedness做key，当key相同时，会自然用输入顺序排列，满足题目要求。

另外，1003,1004,1005,1006,1007这几道题都特别水。。。

#include <iostream><br /> #include <string><br /> #include <map><br /> #include <algorithm><br /> using namespace std;<br /> int unsortedness(const string &);<br /> int main()<br /> {<br /> int length,number;<br /> cin>>length>>number;<br /> multimap<int,string> dmap;<br /> string DNAstr;<br /> int unsort=0;<br /> for(int ix=0;ix<number;++ix)<br /> {<br /> cin>>DNAstr;<br /> unsort=unsortedness(DNAstr);<br /> dmap.insert(make_pair(unsort,DNAstr));<br /> }<br /> for(multimap<int,string>::iterator iter=dmap.begin();iter!=dmap.end();++iter)<br /> {<br /> cout<<iter->second<<endl;<br /> }<br /> return 0;<br /> }<br /> int unsortedness(const string& str)<br /> {<br /> int unsort=0;<br /> for(int i=0;i<str.size()-1;++i)<br /> {<br /> for(int j=i+1;j<str.size();++j)<br /> {<br /> if(str[j]<str[i])<br /> unsort++;<br /> }<br /> }<br /> return unsort;<br /> } 

总结的地方是unsortedness有更高效的算法。

int unsortedness(const string& str)<br /> {<br /> int unsort=0,countA=0,countC=0,countG=0,countT=0;<br /> for(int ix=str.size()-1;ix>=0;--ix)<br /> {<br /> switch(str[ix])<br /> {<br /> case 'A':countA++;<br /> break;<br /> case 'C':countC++;<br /> unsort+=countA;<br /> break;<br /> case 'G':countG++;<br /> unsort+=countA+countC;<br /> break;<br /> case 'T':<br /> unsort+=countA+countC+countG;<br /> break;<br /> default:<br /> exit(1);<br /> }<br /> }<br /> return unsort;<br /> }