ACM1007

题目：DNA序列排序

DNA序列由一序列的大写英文字母表示，如ABCDEF。紊乱程度表示组成DNA序列的字母按照由小到大的顺序进行排列程度，如ABC的紊乱程度比ACB小，因为它字母都是由小到大排序的。紊乱程度计算如下，以DNA序列DCEFB为例：DCEFB的紊乱程度为5，其中字母D右边的序列有2个小于它的字母C和B，字母C有1个小于它的字母B，同理，字母E和F分别有1个排序小于它的字母，紊乱程度=2+1+1+1=5。紊乱程度越大，排序越乱。

程序输入：

第1行输入m和n，其中m表示每一个DNA序列的长度，n表示一共有多少个DNA序列；第2到n行输入DNA序列，每一个DNA序列的长度都为m。m的取值范围为1-100，即DNA序列的长度不超过100，n的范围为1-50，表示最多有50个DNA序列。

结果输出：

按照DNA的紊乱程度由小到大进行排序，如果两个DNA序列的紊乱程度相同，则按照输入的顺序进行排序。

程序设计—（时间16ms，占用空间200k）：

 #include <iostream>

 #include <string>

 using namespace std;

 void qsort(int startIndex,int EndIndex,int *vector,string *values){

     int start=startIndex;

     int end=EndIndex;

     int currentValue = *(vector+start);

     string currentStr = *(values+start);

     while(start<end){

         while(start<end&&*(vector+end)>=currentValue){

             end--;

         }

         *(vector+start)=*(vector+end);

         *(values+start)=*(values+end);

         while(start<end&&*(vector+start)<=currentValue){

             start++;

         }

         *(vector+end)=*(vector+start);

         *(values+end)=*(values+start);

     }

     *(vector+end)=currentValue;

     *(values+end)=currentStr;

     if(end->startIndex){

         qsort(startIndex,end-,vector,values);

     }

     if(end+<EndIndex)

     {

         qsort(end+,EndIndex,vector,values);

     }

 }

 int main()

 {

     char line[];

     string str;

     int *numOfLines=new int[];

     int index=;

     int *values=new int[];

     string *allStr=new string();

     int totalLine=;

     int leterNum=;

     cin>>leterNum>>totalLine;

     numOfLines = new int[totalLine];

     allStr = new string[totalLine];

     values = new int[leterNum];

     while (index<totalLine)

     {

         cin>>line;

         str = line;

         *(allStr+index)=line;

         int count=;

         for(int i=;i<leterNum;i++){

             int l = line[i]-'A';

             *(values+i)=l;

             for(int j=i-;j>=;j--){

                 if(*(values+j)>*(values+i)){

                     count++;

                 }

             }

         }

         (*(numOfLines+index))=count;

         index++;

     }

     qsort(,totalLine-,numOfLines,allStr);

     for(int i=;i<totalLine;i++){

         cout<<*(allStr+i)<<endl;

     }

     return ;

 }

1007是简单题，主要考察一些小细节，有几个需要注意的地方：

（1）数组和指针的问题（由于本人刚刚接触C++，在指针上确实花了一些时间）

数组的指针可以表示第一个元素的位置，然后通过++可以得到其他元素的指针。

如：int *pointer = new int[10];

新建一个10个元素的数组，pointer指向该数组第一个元素的地址，pointer++表示数组第二个元素的地址，pointer+i表示数组第pointer+i个元素。

（2）第二个是输入的问题

弄清楚几个输入的关键方法：

>>、getLine、gets、get_s、fget

巴特西

ACM1007

最新文章

热门文章