题目描述 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 输入格式 第一行为一个单独的整数 n n 表示砍过以后的小木棍的总数。 第二行为 n n 个用空格隔开的正整数，表示 n n 根小木棍的长度。 输出格式 输出仅一行，表示要求的原始木棍的最小可能长度。 输入数据 1 9 5 2 1 5 2 1 5 2 1 输出数据 1 6 数据范围与提示 1 ≤ n ≤ 65 1≤n≤65（ update update：数据已加强） c++14，不要注释，不要编译错误，不要超时，不要queue、pair和vector

分析： 乔治把小木棍随意砍成多段，现在要将它们拼接成原来的样子。我们可以首先求出所有小木棍的总长度，再通过试探法来找到可能的原始木棍最小长度。 具体算法： 1. 读入砍过后的小木棍的总数n。 2. 读入n个小木棍的长度，保存在一个长度为n的数组sticks中。 3. 求出小木棍的总长度total_length。 4. 从1开始逐个试探可能的原始木棍最小长度，设为length。 - 对于每个length，用一个变量curr_sum来记录当前正在拼接的小木棍的长度之和。初始化为0。 - 遍历sticks数组，对于每根小木棍的长度stick，进行以下操作： - 如果当前拼接的小木棍长度之和curr_sum与length相等，说明可以拼接一根小木棍，curr_sum重置为0。 - 如果当前拼接的小木棍长度之和curr_sum比length大，说明无法拼接一根小木棍，当前length不合法，跳出内层循环。 - 否则，继续累加curr_sum。 - 如果所有小木棍都用完了并且curr_sum为0，说明当前length合法，输出length并结束程序。 5. 如果试探完所有可能的length都没有找到符合要求的结果，说明输入数据有误。 时间复杂度分析： 试探法的时间复杂度为O(n)，其中n为小木棍的总数。整个算法的时间复杂度为O(n)。 空间复杂度分析： 需要一个长度为n的数组来保存小木棍的长度，所以空间复杂度为O(n)。 完整代码如下： ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int sticks[65]; int total_length = 0; for (int i = 0; i < n; i++) { cin >> sticks[i]; total_length += sticks[i]; } for (int length = 1; length <= total_length; length++) { int curr_sum = 0; int j = 0; bool valid = true; while (j < n) { curr_sum += sticks[j]; if (curr_sum == length) { curr_sum = 0; } else if (curr_sum > length) { valid = false; break; } j++; } if (valid && curr_sum == 0) { cout << length << endl; return 0; } } cout << "Invalid input" << endl; return 0; } ``` [2024-12-13 19:54:41 | AI写代码神器 | 1278点数解答]