问一下我这个代码，还能怎么优化，为什么时间还超时啊？

Question

总时间限制： 1000ms 内存限制： 65536kB
描述
给定一个正整数 i。编写一个程序来查找位于数字组 S1S2 序列中位置 i 的数字Sk.每个组 Sk 由一系列从 1 到 k 的正整数组成，一个接一个地写出来。
例如，序列的前 80 位数字如下所示：
11212312341234512345612345671234567812345678912345678910123456789101112345678910
输入
输入文件的第一行包含一个整数 t （1 ≤ t ≤ 10），即测试用例的数量，后跟每个测试用例的一行。测试用例的行包含单个整数 i
（1 ≤ i ≤ 2147483647）
输出
每个测试用例应有一行输出，其中包含位于位置 i 的数字。
样例输入
2
8
3
样例输出
2
2

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    vector<char> a;
    char seek(long long x);
    while (n--)
    {
        int x;
        cin >> x;
        a.push_back(seek(x));
    }
    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << endl;
    }
    return 0;
}
char seek(long long x)
{
    long long count = 0;
    string num;
    string str;
    for (int i = 1;; i++)
    {
        if (i == 1)
        {
            num = to_string(i);
            str = to_string(i);
            count += str.length();
        }
        if (i > 1)
        {
            str = to_string(i);
            num = num + str;
            count += str.length();
        }
        if (x > count)
        {
            x -= count;
        }
        else
        {
            return num[x - 1];
            break;
        }
    }
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题解答

你遇到了一个时间超时的问题，可能是因为你的代码的时间复杂度太高了。根据你的描述，问题是要在一个数字组 S1S2 序列中找到位于位置 i 的数字 Sk。

首先，我们可以看到，这个问题可以使用二分查找来解决。我们可以对每个组 Sk 进行二分查找，找到位于位置 i 的数字 Sk。

下面是一个简单的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int search(vector<vector<int>>& S, int i) {
    int k = S.size();
    int left = 1, right = k;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (i < S[mid-1].size() * mid) {
            right = mid - 1;
        } else if (i >= S[mid-1].size() * mid + S[mid].size()) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> S(n);
    for (int i = 0; i < n; i++) {
        S[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            S[i][j] = j;
        }
    }
    int i;
    cin >> i;
    int k = search(S, i);
    if (k != -1) {
        cout << "Sk: ";
        for (int j = 1; j <= S[k-1].size() * k; j++) {
            cout << S[k-1][j % S[k-1].size()] << " ";
        }
        cout << endl;
    } else {
        cout << "Not found" << endl;
    }
    return 0;
}

这个代码首先读取输入的 n 和 m，然后生成一个数字组 S1S2 序列。然后，它使用二分查找来找到位于位置 i 的数字 Sk。最后，它输出 Sk。

这个代码的时间复杂度是 O(log n)，空间复杂度是 O(n)，其中 n 是数字组 S1S2 序列的长度。