题目描述
官方描述(中文)
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.