有n个盒子，编号为1-n，共有a个小球，每个盒子最多可以放一个小球，现将小球放入连续编号的盒子中，用长度为n的数组arra表示n个盒子，1表示该盒子已经被检查过，0表示该盒子未被检查过，用数组arrb表示，

arrb[i]表示第i个盒子是否放有小球，放有为1，没放为0。现在要找出最左边和最右边的放有小球的盒子的编号。

一种解法是从左往右遍历arrb数组，找到第一个放有小球的盒子的编号，记为left。然后从右往左遍历arrb数组，找到第一个放有小球的盒子的编号，记为right。最后返回left和right即可。

时间复杂度为O(n)。

代码示例：

int left = -1, right = -1;
for(int i = 0; i < n; i++){
if(arrb[i] == 1){
left = i+1;
break;
}
}
for(int i = n-1; i >= 0; i--){
if(arrb[i] == 1){
right = i+1;
break;
}
}
return {left, right};

相关问题

编写一个C++程序，解决将n个相同的小球均匀分配到m个不同编号的盒子（每个盒子至少放一个）的所有可能配置，并计算所有配置的方法。能否提供一个示例代码或者算法思路？

在C++中解决这个问题的一个常见策略是使用深度优先搜索（DFS）或广度优先搜索（BFS）。这里我们先用深度优先搜索为例，因为递归是自然的解决方案：

#include <iostream>
using namespace std;

// 用于存储当前状态
struct BoxState {
    int balls[11]; // 假设最多10个球，m=10
    int count; // 当前填满的盒子数量
};

// 动态数组，表示从0到n的所有组合数
int factorial(int n);

// 计算组合数 C(n, k)
int combinations(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// 递归函数，用于生成所有可能的配置
void generateConfigurations(BoxState& state, int ballsLeft, int boxesFilled) {
    if (ballsLeft == 0 && boxesFilled == m) {
        // 所有的球都放在了盒子里，输出配置并计数
        for (int i = 0; i <= m; ++i) {
            cout << "Box " << i << ": " << state.balls[i] << endl;
        }
        cout << "Total configurations: " << state.count << endl;
        return;
    }

    // 从剩余的球中选择一个放入下一个盒子
    for (int i = min(ballsLeft, m - boxesFilled); i > 0; --i) {
        // 将球放入盒子
        state.balls[boxesFilled] = i;
        state.count++;

        // 递归处理剩下的球
        generateConfigurations(state, ballsLeft - i, boxesFilled + 1);

        // 撤销操作，以便尝试其他可能性
        state.balls[boxesFilled] -= i;
        state.count--;
    }
}

// 计算阶乘
int factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    int n, m;
    cout << "Enter the number of balls (n): ";
    cin >> n;
    cout << "Enter the number of boxes (m): ";
    cin >> m;

    BoxState initialState;
    initialState.count = 0;
    generateConfigurations(initialState, n, 0);
    return 0;
}

这个程序首先读取球的数量 `n` 和盒子的数量 `m`，然后初始化一个结构体 `BoxState` 来记录每一步的状态。递归函数 `generateConfigurations` 负责生成所有可能的配置，每次递归时都会尝试把一个球放到下一个未满的盒子中，直到所有的球都被分完。最后，在主函数中调用该函数开始探索。

注意：这个代码假设了球和盒子的数量都不大，如果数据范围较大，可能需要优化存储或使用更高效的算法。