题目描述

官方描述(中文)
2021/09/10每日一题

思路

前缀和+二分查找

代码

class Solution 
{
public:
    int chalkReplacer(vector<int>& chalk, int k)
	{
		if (chalk.size() <= 0 || chalk[0] > k)return 0;
		vector<int>perVec(chalk.size(), 0);
		perVec[0] = chalk[0];
		for (int i = 1; i < chalk.size(); ++i)
		{
			perVec[i] += chalk[i] + perVec[i - 1];
			if (perVec[i] > k)return i;
		}
		k %= perVec[perVec.size() - 1];

		auto iter = upper_bound(perVec.begin(), perVec.end(), k);
		return iter - perVec.begin();
	}
};

执行结果

Q.E.D.