DividingStrings - 题解

标签与难度

标签: 贪心, 字符串, 大数处理, 思维题, 构造, 前缀和难度: 1900

题目大意喵~

你好呀，指挥官！这里是你的专属我小助手，喵~ 我们接到了一个有趣的任务！

ZYB 同学有一个长长的数字串 s，长度为 n。他想把这个字符串切成好几段（至少两段），每一段都代表一个十进制数。我们的目标是，让这些数字中最大值和最小值的差变得最小最小，就像把小鱼干分得最均匀一样，喵~

有几个小规则需要注意哦：

分割成的子串不能为空。
子串不能有前导零，除非这个子串本身就是 "0"。比如说，'01' 是不可以的，但是 '0' 是可以的。像 '001' 这样的字符串，就只能乖乖地被切成 '0', '0', '1' 三段呢。

我们需要找到这个最小的差值。

举个栗子：如果字符串是 '1230'，我们可以切成 '12' 和 '30'。这两个数的值就是 12 和 30，差值是 18。我们能找到比这更小的差值吗？也许可以哦！

解题思路分析

这道题看起来有点棘手呢，数字串 s 的长度 n 可以到 200,000，形成的数字可能会非常非常大，用普通的 long long 都装不下，喵~ 而且分割方案那么多，直接暴力搜索肯定会超时的。

不过别担心，让我来分析一下问题的核心！我们要最小化 max_val - min_val。我们来观察一下数字的特性，特别是它们的长度。

一个 L 位的数字，和一个 L+k 位的数字，当 k 比较大的时候，它们的值会差很多！比如说，一个 1 位数（最大是 9）和一个 3 位数（最小是 100），它们的差值至少是 100 - 9 = 91。这个差值也太大了！相比之下，如果我们把一个字符串比如 1009 切成 1, 0, 0, 9，那么最大值是 9，最小值是 0，差值只有 9。

这给了我们一个超级重要的启示，喵！为了让差值尽可能小（特别是小于10），分割出来的所有数字的长度必须非常接近。具体来说，它们的长度差最多只能是 1！如果长度差达到 2 或以上，那么差值一定会超过 10，肯定不是最优解啦。

于是，问题就被我们简化成了两种情况，呐：

情况一：所有数字的长度都相同

如果所有分割出来的数字长度都是一样的，比如说长度都是 L，那么 L 必须是 n 的一个因数。我们可以遍历 n 的所有因数 L (其中 L < n)。对于每个 L，我们将字符串 s 切成 n/L 个长度为 L 的小段。然后，我们就在这些小段中找到字典序最大和最小的两个。因为它们都是大数，所以我们不能直接转成 int 比较，而是要用字符串或者大数减法来处理。我们可以写一个简单的大数减法函数，计算出 max_string - min_string 的值。如果这个差值大于 9（也就是说，结果不止一位数），那它肯定不是最优解。如果差值是 0-9 之间，我们就用它来更新我们的最小差值答案。

情况二：数字的长度只可能是 L 和 L+1

这种情况稍微复杂一点点，但原理是相通的。要想让一个 L 位数和一个 L+1 位数的差值最小，它们必须是什么样的数呢？当然是最大的 L 位数和最小的 L+1 位数啦！也就是 99...9 (L个9) 和 10...0 (1后面L个0)。它们的差值仅仅是 1！所以，一个优秀分割方案里的数字，肯定都长得和 99...9 或者 10...0 很像。

基于这个想法，我们可以尝试用一种贪心的方式来验证。我们遍历所有可能的基准长度 L (从 1 到 n/2)。对于每个 L，我们检查整个字符串 s 是否可以被看作是一系列 “伪 9...9” (长度L) 和 “伪 10...0” (长度L+1) 的组合。

“伪 10...0” 是指：一个长度为 L+1 的数，它以 '1' 开头，后面跟着 L-1 个 '0'，最后一位可以是任意数字。例如，L=3 时，1002 就是一个 “伪 10...0”。
“伪 9...9” 是指：一个长度为 L 的数，它的前 L-1 位都是 '9'，最后一位可以是任意数字。例如，L=3 时，997 就是一个 “伪 9...9”。

我们可以从头到尾扫描字符串 s：

在当前位置，优先检查是否能匹配一个长度为 L+1 的 “伪 10...0”。
如果不行，再检查是否能匹配一个长度为 L 的 “伪 9...9”。
如果两种都匹配不上，说明这个 L 不可行，我们就放弃它，继续尝试下一个 L。
如果成功地把整个字符串 s 都匹配完了，我们就找到了一个合法的分割。这时，我们需要计算这个分割方案下的 max - min。
- 最大值，就是所有 “伪 10...0?” 中最后一位数字最大的那个，我们称之为 max_tail_1。这个数的值是 $10^L + max\_tail\_1$ 。
- 最小值，就是所有 “伪 9...9?” 中最后一位数字最小的那个，我们称之为 min_tail_9。这个数的值是 $10^L - (9 - min\_tail\_9)$ 。
- 差值就是 $(10^L + max\_tail\_1) - (10^L - 1 - min\_tail\_9) = max\_tail\_1 + min\_tail\_9 + 1$ 。不对哦，我算错了...应该是 $(10^L + max\_tail\_1) - (10^L - (9 - min\_tail\_9)) = max\_tail\_1 + 9 - min\_tail\_9$ ... 还是不对！
- 让我们重新理一理！max_val 来自于 10...0 家族或者 9...9 家族。min_val 也一样。最可能产生最小差值的是 max_val 来自 10...0 家族，min_val 来自 9...9 家族。
- 最大值是 $10^L + max\_tail\_1$ 。最小值是 $10^L - 1 - (8 - min\_tail\_9)$ ... 太复杂了！
- 让我们看参考代码里的聪明做法！10 - nine + zero。zero 是 10...0? 里 ? 的最大值，nine 是 9...9? 里 ? 的最小值。
- 最大数是 $10^L + zero$ 。最小数是 $10^L - (9-nine) - 1$ ? 不对，是 $10^L - (10 - (nine+1)) = 10^L - 9 + nine$ 。
- 啊哈！max_val = 10...0_max_tail = 1 \cdot 10^L + max_tail_1。min_val = 9...9_min_tail = 1 \cdot 10^L - 1 - (9 - min_tail_9) = 10^L - 10 + min_tail_9。
- max_val - min_val = (10^L + max_tail_1) - (10^L - 10 + min_tail_9) = max_tail_1 - min_tail_9 + 10。这和代码 10 - nine + zero 完全一致！喵~ 看来这个思路是正确的！

特殊情况 如果字符串以 '0' 开头，根据规则，任何以 '0' 开头的子串长度必须为 1。这意味着如果 s[0] == '0'，唯一的合法分割就是把整个字符串切成 n 个单字符。此时的答案就是所有单个数字中的最大值减去最小值。

现在，我们的策略清晰了：

处理 s[0] == '0' 的特殊情况。
遍历 L 从 1到 n/2：
- 调用 solve_for_adjacent_lengths(L) 检查长度为 L 和 L+1 的情况。
- 如果 n % L == 0，调用 solve_for_same_length(L) 检查长度全为 L 的情况。
在所有可能的结果中取最小值，就是最终答案啦！

为了快速判断一个子串是不是全是 '0' 或者全是 '9'，我们可以预处理一个数字前缀和数组，这样就能 $O(1)$ 查询啦！

代码实现

这是我根据上面的思路，精心重构的一份代码哦，希望能帮助你理解，喵~

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 全局变量，方便函数调用
int n;
string s;
vector<int> a; // 存储字符串s的数字形式
vector<int> prefix_sum; // 数字前缀和

// 大数减法，计算 str_max - str_min
// 返回值是 string 类型，但我们只关心个位数，所以返回 int
// 如果差值 >= 10，返回一个特殊值（比如10）
int big_num_subtract(const string& str_max, const string& str_min) {
    int len = str_max.length();
    vector<int> res(len);
    int borrow = 0;
    for (int i = len - 1; i >= 0; --i) {
        int digit_max = str_max[i] - '0';
        int digit_min = str_min[i] - '0';
        int diff = digit_max - digit_min - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res[i] = diff;
    }

    // 检查差值是否大于9
    for (int i = 0; i < len - 1; ++i) {
        if (res[i] != 0) {
            return 10; // 差值 >= 10，不是我们想要的
        }
    }
    return res[len - 1];
}

// 情况一：所有数字长度都为 L
int solve_for_same_length(int L) {
    // 检查是否有前导零 (除了L=1的情况)
    if (L > 1 && s[0] == '0') return 10;

    string min_str = s.substr(0, L);
    string max_str = s.substr(0, L);

    for (int i = L; i < n; i += L) {
        // L > 1时，任何子串都不能以'0'开头
        if (L > 1 && s[i] == '0') {
            return 10; // 无效分割
        }
        string current_str = s.substr(i, L);
        if (current_str < min_str) {
            min_str = current_str;
        }
        if (current_str > max_str) {
            max_str = current_str;
        }
    }
    
    return big_num_subtract(max_str, min_str);
}

// 检查子串 s[start..end] 是否全为 digit
bool is_all_digit(int start, int end, int digit) {
    if (start > end) return true;
    int expected_sum = (end - start + 1) * digit;
    int actual_sum = prefix_sum[end + 1] - prefix_sum[start];
    return actual_sum == expected_sum;
}


// 情况二：数字长度为 L 或 L+1
int solve_for_adjacent_lengths(int L) {
    int current_pos = 0;
    int max_tail_for_10_family = 0; // 对应 '10...0?' 的 '?'
    int min_tail_for_9_family = 9;  // 对应 '9...9?' 的 '?'
    bool found_10_family = false;
    bool found_9_family = false;

    while (current_pos < n) {
        // 优先匹配长度为 L+1 的 "10...0?" 模式
        // 条件: 长度足够 & 第一位是'1' & 中间 L-1 位是'0'
        if (current_pos + L < n && a[current_pos] == 1 && is_all_digit(current_pos + 1, current_pos + L - 1, 0)) {
            max_tail_for_10_family = max(max_tail_for_10_family, a[current_pos + L]);
            current_pos += (L + 1);
            found_10_family = true;
        } 
        // 匹配长度为 L 的 "9...9?" 模式
        // 条件: 长度足够 & 前 L-1 位是'9'
        else if (current_pos + L - 1 < n && is_all_digit(current_pos, current_pos + L - 2, 9)) {
            min_tail_for_9_family = min(min_tail_for_9_family, a[current_pos + L - 1]);
            current_pos += L;
            found_9_family = true;
        } 
        // 两种模式都匹配不上，说明这个L不行
        else {
            return 10;
        }
    }

    // 如果只找到一种类型的数字，差值为0
    if (!found_10_family || !found_9_family) {
        // 但题目要求至少分两段，如果只找到一种模式且只形成一个数，是不合法的
        // 不过我们的循环L从1到n/2，保证了至少两个数，所以这种情况差值为0
        return 0;
    }
    
    return 10 + max_tail_for_10_family - min_tail_for_9_family;
}

void solve() {
    cin >> n >> s;

    a.resize(n);
    prefix_sum.assign(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        a[i] = s[i] - '0';
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }
    
    // 特殊情况：以'0'开头，只能切成单个数字
    if (s[0] == '0') {
        int min_digit = 9, max_digit = 0;
        for (int digit : a) {
            min_digit = min(min_digit, digit);
            max_digit = max(max_digit, digit);
        }
        cout << max_digit - min_digit << endl;
        return;
    }

    int min_diff = 9; // 初始答案最大为9 (e.g. '90')

    for (int L = 1; L <= n / 2; ++L) {
        // 检查情况二
        min_diff = min(min_diff, solve_for_adjacent_lengths(L));
        
        // 如果 L 是 n 的因数，检查情况一
        if (n % L == 0) {
            min_diff = min(min_diff, solve_for_same_length(L));
        }
    }
    cout << min_diff << endl;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + N \cdot d(N))$ ，其中 $d(N)$ 是 $N$ 的约数个数。
- 主循环遍历长度 L 从 1 到 N/2。
- solve_for_adjacent_lengths(L) 函数内部是一个 while 循环，每次指针 current_pos 至少前进 L，所以循环次数约为 N/L。总的时间贡献是 $\sum_{L=1}^{N/2} O(N/L)$ ，这近似于 $O(N \log N)$ 。
- solve_for_same_length(L) 函数只在 L 是 N 的约数时被调用。函数本身需要 $O(N)$ 的时间（字符串操作和遍历）。总的时间贡献是 $O(N \cdot d(N))$ 。
- $d(N)$ 在最坏情况下也远小于 $N$ ，所以总体复杂度是高效的，可以通过本题，喵~
空间复杂度: $O(N)$
- 我们使用了几个大小为 $N$ 的辅助数组 (a 和 prefix_sum) 来存储数字和前缀和。所以空间复杂度是线性的。

知识点总结

这道题真是一次有趣的思维探险呢！我们来总结一下学到的东西吧：

问题简化: 面对复杂的问题，尝试从特殊性质入手。本题的关键就是发现最优解中各数字的长度差非常小（最多为1），这极大地缩小了搜索范围。
分类讨论: 将问题分解为“所有数字等长”和“长度差为1”两种情况，使得逻辑更清晰，实现也更简单。
构造与贪心: 在处理“长度差为1”的情况时，我们构造出了 9...9 和 1...0 这种理想模型，并用贪心策略去匹配字符串，这是一种非常强大的构造性思维。
大数处理技巧: 对于可能超出整型范围的大数，不一定需要完整的大数库。根据问题需求，可以使用字符串比较、或者像本题一样实现一个简单的、只关心小差值的减法。
前缀和优化: 使用前缀和可以 $O(1)$ 地判断一个区间的数字之和，从而快速检查一个子串是否由同一个数字（如'0'或'9'）组成，这是个常用的小技巧哦！

希望这篇题解能帮到你，如果还有问题，随时可以再来找我哦，喵~ 🐾

DividingStrings - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​