POJ ( acm.pku.edu.cn ) 1007

这道题也有点诡异，G++ 的 STL 中的 stable_sort 似乎不能正常工作。

另外，计算逆序其实可以以 nlogn 的时间复杂度完成；拷贝构造函数如果使用引用计数之类的方式可以提高效率——所以优化的空间还很大。

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

class DNA {
public:
  char str[51];
  int  inv;
  DNA(char const* s=""){strcpy(str,s); inv=ninv(); }
  DNA(DNA const& d){strcpy(str,d.str); inv=d.inv;}
  int ninv(){
      int n=0;
      for(char const* i=str;*i;++i)
          for(char const*j=i;*j;++j)
              if(*i>*j)
                  ++n;
      return n;
  }
  bool operator<(DNA const& b) const {
      return this->inv<b.inv;
  }
};

int main()
{
  int N,M; char temp[51];
  vector<DNA> dnas;
  for(cin>>N>>M;M;--M){
      cin>>temp;
      dnas.push_back(DNA(temp));
  }
  std::stable_sort(dnas.begin(), dnas.end());
  for(vector<DNA>::const_iterator i=dnas.begin();i!=dnas.end();++i){
      cout<<i->str<<endl;
  }
  return 0;
}