题解 | #诗#_牛客博客

题目链接

诗

题目描述

给定一个由小写字母组成的字符串 $S$ 。按照以下规则将字符串分行书写：

第一行：书写接下来的 1 个字母。
第二行：书写接下来的 2 个字母。
第三行：书写接下来的 3 个字母。
...
第 $k$ 行：书写接下来的 $k$ 个字母。
以此类推，直到字符串中的所有字符都被写完。如果某一行需要 $k$ 个字符，但剩余字符不足 $k$ 个，则将所有剩余字符写在这一行后停止。

任务是收集每一行的首字母，并按顺序连接成一个新的字符串作为答案。

解题思路

这是一个简单的模拟题。我们可以按照题目描述的规则，一步步地从原始字符串中提取字符并构建答案。

我们需要维护两个变量来追踪整个过程：

一个指针 current_index，记录当前我们在原始字符串 $S$ 中处理到的位置。初始时，current_index 指向字符串的开头，即索引 0。
一个计数器 take_count，记录当前这一行需要书写多少个字符。根据规则，第一行需要 1 个，第二行 2 个，以此类推。所以 take_count 初始为 1。

算法流程:

初始化 current_index = 0，take_count = 1，以及一个空的答案字符串 ans。
进入一个循环，循环的条件是 current_index 必须小于字符串 $S$ 的总长度 $N$ ，确保我们还有字符可以处理。
在每一次循环中，我们模拟“书写新的一行”：
- 当前行的首字母就是位于 S[current_index] 的字符。我们将这个字符追加到 ans 的末尾。
- 书写完这一行后，我们在原始字符串中的位置需要向后移动。移动的距离就是 take_count。所以，更新 current_index = current_index + take_count。
- 为下一行做准备，需要书写的字符数会增加 1。所以，更新 take_count = take_count + 1。
循环会一直进行，直到 current_index 大于或等于 $N$ ，此时所有字符都已被分配，模拟结束。
最终得到的 ans 字符串即为所求的答案。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    string ans = "";
    int current_index = 0;
    int take_count = 1;
    int n = s.length();

    while (current_index < n) {
        ans += s[current_index];
        current_index += take_count;
        take_count++;
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        StringBuilder ans = new StringBuilder();
        int currentIndex = 0;
        int takeCount = 1;
        int n = s.length();

        while (currentIndex < n) {
            ans.append(s.charAt(currentIndex));
            currentIndex += takeCount;
            takeCount++;
        }

        System.out.println(ans.toString());
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    
    ans = []
    current_index = 0
    take_count = 1
    n = len(s)
    
    while current_index < n:
        ans.append(s[current_index])
        current_index += take_count
        take_count += 1
        
    print("".join(ans))

solve()

算法及复杂度

算法: 模拟
时间复杂度: 设字符串长度为 $N$ 。在循环中，指针 current_index 的值依次增加 1, 2, 3, ...。假设循环进行了 $k$ 次，那么 current_index 的值约等于 $1+2+...+k = \frac{k(k+1)}{2}$ 。当这个值超过 $N$ 时循环停止，即 $\frac{k^2}{2} \approx N$ ，解得 $k \approx \sqrt{2N}$ 。因此，循环执行的次数约为 $\mathcal{O}(\sqrt{N})$ ，总时间复杂度为 $\mathcal{O}(\sqrt{N})$ 。
空间复杂度: 我们需要一个额外的字符串来存储答案。答案字符串的长度与循环次数相同，即 $\mathcal{O}(\sqrt{N})$ 。因此，空间复杂度为 $\mathcal{O}(\sqrt{N})$ 。