练64.3 打印沙漏

解题思路

半边含中心共k行时，符号总数为2k²-1，最大宽2k-1。取满足总数≤N的最大k，再先递减后递增输出宽度，最后N-(2k²-1)为剩余。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

中心行只打印一次；行首补缩进，右边不补空格。

复杂度

时间O(N)，临时串空间O(√N)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    char c;
    cin >> N >> c;
    int k = 1;
    while (2 * (k + 1) * (k + 1) - 1 <= N)
        k++;
    for (int i = 0; i < 2 * k - 1; i++) {
        int d = min(i, 2 * k - 2 - i);
        cout << string(d, ' ') << string(2 * (k - d) - 1, c) << "\n";
    }
    cout << N - (2 * k * k - 1) << "\n";
    return 0;
}