力扣刷题——3096.得到更多分数的最少关卡数目

根据题意，假如alice选择完成第i关到第j关，那么bob需要完成第j+1关到第n关，其中i<=j<n。如此可以想到对关卡数组进行预处理，构建一个前缀和数组，保存假如从第0关每关都通过的话，到第i关所得到的分数。
通过遍历一次前缀和数组，能够得到每个时刻alice得到的分数和bob得到的分数，当alice获得的分数超过了bob那么就可以直接输出结果，假如遍历完成后仍然没有alice得分高于bob得分的情况，那么就输出-1。

class Solution
{
public:
    int minimumLevels(vector<int> &possible)
    {
        vector<int> preSum;
        int totalSum = possible[0] == 1 ? 1 : -1;
        preSum.emplace_back(0);
        int alicePlay = 1;
        for (int i = 1; i < possible.size(); i++)
        {
            preSum.emplace_back(totalSum);
            totalSum += possible[i] == 1 ? 1 : -1;
        }
        while (alicePlay < preSum.size())
        {
            if (preSum[alicePlay] > totalSum - preSum[alicePlay])
                return alicePlay;
            alicePlay++;
        }

        return -1;
    }
};