关于算法-数据结构: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;
}