# 1769.移动所有球到每个盒子所需的最小操作数

## 问题描述
[1769.移动所有球到每个盒子所需的最小操作数](https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/)

## 解题思路
暴力求解，时间复杂度为$\Theta(n^2)$;

可以考虑利用前缀和来降低时间复杂度:
设`nums[i]`是前`i + 1`个盒子里的球的总个数，`res[i]`为将所有球移到第`i + 1`个盒子里所需要的操作数，`sum`为球总个数，移到第`i + 1`个盒子相比移到第`i`个盒子，左边的球各要多移一步，右边的球各少移一步，因此有那么有:`res[i] = res[i - 1] + nums[i - 1] - (sum - nums[i - 1])`，

## 代码
```cpp
class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int> nums(boxes.size(), 0);
        int sum = boxes[0] - '0';
        nums[0] = boxes[0] - '0';
        for (int i = 1; i < boxes.size(); i++) {
            if (boxes[i] == '1') {
                nums[i] = nums[i - 1] + 1;
                sum++;
            } else
                nums[i] = nums[i - 1];
        }
        vector<int> res(boxes.size(), 0);
        for (int i = 1; i < boxes.size(); i++) {
            res[0] += i * (boxes[i] - '0');
        }
        for (int i = 1; i < boxes.size(); i++) {
            res[i] = res[i - 1] + nums[i - 1] - (sum - nums[i - 1]);
        }
        return res;
    }
};
```