乐趣区

关于算法-数据结构:PAT甲级1031-Hello-World-for-U

题目粗心:

将给定字符串按 U 形进行输入。其中 n1 为左侧竖线蕴含的字符数,n2 为底部横线蕴含的字符数,n3 为右侧竖线蕴含的字符数,且 n1、n2、n3 均蕴含拐角处相交的字符,于是有 n1+n2+n3=N+ 2 恒成立。此外,对 n1、n2、n3 有如下的限制性条件:

  1. n1=n3,即左侧竖线蕴含的字符数等于右侧竖线蕴含的字符数。
  2. n2≥n1, 即底部横线蕴含的字符数总是不少于左、右单侧竖线蕴含的字符数。
  3. 在满足下面两个条件的前提下,使 n1 尽可能大。
算法思路:

首先得获取 n1,n2 和 n3, 获取的办法是从小到大遍历 n2,这样对于 n1 和 n3 来说就是从大到小变动,在 (N+2-n2) 能够整除 2 的状况下,第一次满足的 n1<=n2 必然是最大的 n1。而后再依照每一行进行输入,对于第 1 到 n1- 1 行,都是左右两边一个字符,两头 n2- 2 个空格,最初一行为 n2 个字符。为此应用 index 标记最右边的待输入字符的地位,对于第 1 到 n1- 1 行,第一个字符为 s[index], 最左边的字符则为 s[N-1-index],最初一行的输入间接输入 n2 个 s[index++]即可。

提交后果:

AC 代码:
#include<cstdio>
#include<cstring>

using namespace std;

int main(){char s[90];
    scanf("%s",s);
    int N = strlen(s);// 字符串的长度 
    int n1,n2,n3;//2n1+n2=N+2 ,n1 为小于 n2 的最大值 
    // 遍历 n2 获取 n1,n3
    for(n2=3;n2<=N;++n2){if((N+2-n2)%2==0){n1 = (N+2-n2)/2;
            n3 = n1;
            if(n1<=n2){break;}
        }
    } 
    int index = 0;// 标记以后待输入字符的地位(从左往右) 
    // 输入后果, 除了最初一行,其余的每一行都是输入一个字符,n2- 2 个空格, 一个字符 
    for(int i=0;i<n1-1;++i){printf("%c",s[index]);
        for(int j=0;j<n2-2;++j){printf(" ");
        } 
        printf("%c\n",s[N-1-index]);
        ++index;
    } 
    // 输入最初一行
    for(int i=0;i<n2;++i){printf("%c",s[index++]);
    } 
    return 0;
}
退出移动版