第8周题解

第8周题解

三值排序

题目大意：给定一串数，其中只包含1,2,3，编程计算给定的1,2,3序列，排成升序最少要经过多少步。

分析：首先，因为数列中只包含1,2,3，所以我们可以分别统计出1,2,3的个数，然后进行判断：因为排好后的顺序肯定是111…222…333…，所以，1的个数加一个就是2的起始位置，同理，3也是如此。我们从1的起始位置1循环到结束的位置，若枚举到有2出现，就在2的区间内找1，然后计数器sum加1，然后用同样的方式在1的区间内找1，在3的区间内找1，累加。找完1后按同样方法找2内的3.

代码如下：

#include<bits/stdc++.h>

usingnamespace std;

intmain()

{

       inta[1010]={},n=0,s[4]={},c=0,k=0,x=0,sum=0;

       cin>>n;

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

       {

              cin>>a[i];

              s[a[i]]++;//统计1,2,3的个数

       }

       c=s[1]+1;//2数字的起始位置

       x=n;//由于3的位置无法确定，所以从后开始枚举

       for(int i=1;i<=s[1];i++)

       {

              if(a[i]==2)//在1的范围内找2

               {

                    while(a[c]!=1)c++;//找2中的1

                    k=a[i];//交换

                    a[i]=a[c];

                    a[c]=k;

                    sum++;//累加交换次数

               }

               else if(a[i]==3)//同理，找3

               {

                    while(a[x]!=1)x--;//从3的末尾也就是数组的最后开始找

                    k=a[i];//交换

                    a[i]=a[x];

                    a[x]=k;

                    sum++;//累加

               }

       }

       for(int i=s[1]+1;i<=s[1]+s[2];i++)//2里找3

       if(a[i]==3)

        sum++;//最后只要知道次数，所以累加即可，不用交换

       cout<<sum<<endl;

       return 0;

}

这题坑倒是没有，理解题意就简单了。

 

倒数字三角形

以下的数字倒直角三角形是由二个数确定的：一个数是行数R，1<=R<=39，另一个是种子数S,1<=S<=9。S放在左上角，照着样例输出文件的样子，写一个程序，根据输入的二个数打印出相应的数字倒直角三角形。

输入格式

单独一行，二个用空格隔开的整数

 

输出格式

输出倒直角数字三角形，输出时数字与数字之间不留空格字符。

 

样例数据

input

 

6 1

output

 

124727

 35838

  6949

   151

    62

     3

分析：这题有坑！！！从种子数开始到9之后又会从1开始循环，这个要注意，其他很简单，找到规律按题意模拟即可，具体规律由代码呈现。

代码如下：

#include<bits/stdc++.h>

usingnamespace std;

intmain()

{

       int r;

       char k,s;//注意，k和s是字符

       char a[100][100];

       cin>>r>>s;

       for(int i=1;i<=r;i++)

        for(int j=1;j<=r;j++)

        a[i][j]=' ';//将二维数组的值都设成空格，不要问我为什么，下面你就知道了

       k=s;

       for(int i=1;i<=r;i++)//循环列数

        for(int j=1;j<=i;j++)//第一列有1个数，第二列有2个数，以此类推，第i行有i个数

         {

             a[j][i]=k;

             k++;

             if(k=='9'+1)//k是字符，所以必须加引号，否则你的输出里将会是非常可人的笑脸

              k='1';//到9之后从1开始，千万别忘了

         }

       for(int i=1;i<=r;i++)//输出

       {

              for(int j=1;j<=r;j++)

               cout<<a[i][j];//由于二维数组中除字符外就是空格，所以直接输出，刚好符合题意。

              cout<<endl;

       }

       return 0; 

}