C/C++语言算法题—

【问题】

Description

给定一个有限长度的非负整数序列。一次操作是指从第一个元素开始，依次把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。总有一个时刻该数列将不再发生改变（即此时每个数都恰好等于它右边比它小的数的个数）。例如给定数列：
5, 44, 19, 6, 49, 1, 27, 19, 50, 20
连续进行五次操作后，依次得到新数列如下：

1, 6, 2, 1, 4, 0, 2, 0, 1, 0
3, 8, 5, 3, 5, 0, 3, 0, 1, 0
4, 8, 6, 4, 5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1, 0

其中，第四次操作后，数列不再发生改变。
对给定数列，循环执行上述操作，直到其不再改变为止，输出最后得到的数列。

Input

第1行：一个整数T（1≤T≤10）为问题数。
对于每组测试数据：
第1行是一个正整数：数列长度N ( 2 < N≤30 )；
第2行有N个正整数：分别为该数列第1至第N个元素的值a1,a2,…,aN( a1,a2,…, aN均为1 - 1000的数)，每两个整数之间用一个空格分开。

Output

对于每个问题，输出一行问题的编号（0开始编号，格式：case #0: 等）。
然后在一行中依次输出最后数列的所有元素，每两个元素之间用一个空格分开，最后一个元素后面没有空格。

Sample Input

3
10
5 44 19 6 49 1 27 19 50 20
10
3 2 7 10 9 8 8 5 1 5
10
12 12 19 19 7 10 9 6 18 9

Sample Output

case #0:
5 8 7 5 5 0 3 0 1 0
case #1:
9 2 3 6 5 3 3 2 0 0
case #2:
6 6 6 6 3 4 3 0 1 0

【解题报告】

算法本身很容易实现，但是问题是我不清楚应当如何判断算法何时结束，也就是如何判断“两次变换所得到的新数组相等”。如果有更好的算法请不吝赐教。

 #include <iostream>

 using namespace std;

 #define TRUE 1

 #define FALSE 0

 int isSame(const int*, const int*, const int);

 void setArray(int*, int);

 void outputArray(const int*, const int);

 void process(int*, int);

 int* clone(const int*, int);

 int main()

 {

     int T;

     cin>>T;

     for(int c = ; c < T; c++)

     {

         int N;

         cin>>N;

         int* arr = new int[N];

         setArray(arr,N);

         for(;;)                            /* 这里我实在想不出该如何简便地判断参加变换的数组是否发生变化，因此 */

         {                                /* 只能通过备份前一次变换的结果和当次运算结果作比较 */

             int* temp = clone(arr,N);

             process(arr,N);                /* 虽然能够AC，但是这肯定不是最优的算法 */

             if(isSame(arr,temp,N))      /* 因此如有更好的，时间复杂度更低的算法还望不吝赐教奥 */

             {

                 delete[] temp;

                 break;

             }

         }

         cout<<"case #"<<c<<":"<<endl;

         outputArray(arr,N);

         delete[] arr;

     }

     return ;

 }

 /** 判断两个同等长度的数组是否相等

   @param arr1 数组1

   @param arr2 数组2

   @param N 数组1和2的长度

   @returns 相等返回1，否则返回0

 */

 int isSame(const int* arr1, const int* arr2, const int N)

 {

     for(int i = ; i < N; i++)

     {

         if(arr1[i] != arr2[i])

             return FALSE;

     }

     return TRUE;

 }

 /**

  通过标准输入设置数组的各元素

  @param arr 待填充的数组

  @param n   数组长度

 */

 void setArray(int* arr, int n)

 {

     int t;

     for(int i = ; i < n; i++)

     {

         cin>>t;

         arr[i] = t;

     }

 }

 /**

   输出数组

   @param arr 要输出的数组

   @param N 数组长度

 */

 void outputArray(const int* arr, const int N)

 {

     for(int i = ; i < N; i++)

     {

         cout<<arr[i];

         if(i != N-) cout<<' ';

         else cout<<'\n';

     }

 }

 /**

   处理算法

   循环处理每一个元素，将其修改为它后面比它小的元素的个数

   @param arr 要处理的数组

   @param N 数组长度

 */

 void process(int* arr, int N)

 {

     for(int i = ; i < N; i++)

     {

         int count = ;

         for(int j = i+; j < N; j++)

         {

             if(arr[j] < arr[i])

                 count++;

         }

         arr[i] = count;

     }

 }

 /**

   克隆数组，将一个数组克隆为另一个数组，

   使得两个数组中的各元素相同，但他们的首指针不同。

   @param arr 待克隆的源数组

   @param N   数组长度

   @returns   克隆出的新数组

 */

 int* clone(const int* arr, int N)

 {

     int* temp = new int[N];

     for(int i = ; i < N; i++)

     {

         temp[i] = arr[i];

     }

     return temp;

 }解题代码

解题代码

【优化】

根据hoodlum1980的建议。将process函数改为

bool process(int* arr, int N)

{

    bool changed = false;

    for(int i = ; i < N; i++)

    {

        int count = ;

        for(int j = i+; j < N; j++)

        {

            if(arr[j] < arr[i])

                count++;

        }

        if(arr[i] != count)

        {

            arr[i] = count;

            changed = true;

        }

    }

    return changed;

}

主函数相应部分改为

while(process(arr,N));

出处：http://acm.cs.ecnu.edu.cn/problem.php?problemid=2993

巴特西

C/C++语言算法题——替换