题目找到需要补充粉笔的学生编号

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量严格小于 chalk[i] ，那么学生 i 需要补充粉笔。

请你返回需要补充粉笔的学生编号。

以下为题目给出的两个示例
在这里插入图片描述

附题目链接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk/

解题思路

首先，拿到这道题，最直接的思路就是不断遍历数组，每次循环时直接 k -= chalk[i]；但这样如果数组很小，而k很大时，我们需要遍历很多次，这种暴力的解法会使得时间复杂度过大，甚至无法通过。因此，诞生了最佳的模拟解法：

模拟解法

我们不妨对其数组求和，然后将初始粉笔数k 对总和取余，然后再进行一次遍历数组，这样子的时间复杂度就是O（2*n） = O（n），n表示数组的尺寸。这样子最多循环遍历两次数组即可完成
代码如下

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int n = chalk.size();
        long long sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum += chalk[i];
        }
        k  %= sum;
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            if(k < chalk[i])
            {
                ans = i;
                break;
            }
            k -= chalk[i];
        }
        return ans;
    }
};

个人觉得代码较简单，所以没有做注释（其实就是当时懒）
但是还可以比这种方法更快的解法，当然，不是那种面向结果（指用if语句涵盖所有的测试案例）的解法，而是我们今天的主角：

前缀和+二分查找

思路：我们不妨先便历一次数组，每次求数组的前缀和，但是这样会有一个问题，其实前面的解法，小伙伴们如果细心的话就会发现我对于sum变量是用了long long 超长整型的，因为在加和的过程中可能会出现结果超过int的范围，但是我们的初始粉笔数k是int型，也就是如果出现了大于int的前缀和，那一定会比k大，进一步如果前缀和严格大于k，那么当前下标即为所求编号。而如果退一步，如果最后前缀和依然比k小，那不妨将k也和最后的前缀和（相当于数组总和）做取余操作，然后再在数组遍历查找，但是这样子不就和模拟解法一样了吗？这时我们可以引入二分思想来查找数组下标，使得复杂度再一次降低。
代码（完整，涵盖输入）如下

#include<iostream>
#include<vector>
using namespace std;

// 前缀和 + 二分查找解法
// 解决方案——类
class Solution
{
public:
	// 定义二分查找函数
	int binary_search(vector<int>& nums, int k)
	{
		// 声明左、右下标
		int l = 0, r = nums.size() - 1;
		while (l < r)
		{
			// 中间下标
			int m = l + (r - l) / 2;
			// 刚好相等
			if (nums[m] == k)
			{
				return m + 1;
			}
			else if (nums[m] < k)
			{
				l = m + 1;
			}
			else if (nums[m] > k)
			{
				r = m;
			}
		}
		// 二分确定的右下标即为所求下标（严格大于！）
		return r;
	}

	int chalkReplacer(vector<int>& chalk, int k)
	{
		// 获取学生人数
		int n = chalk.size();
		// 特殊情况，k严格小于第一个学生需要的粉笔数
		if (k < chalk[0])
		{
			return 0;
		}
		// 计算前缀和
		for (int i = 1; i < n; i++)
		{
			chalk[i] += chalk[i - 1];
			// 判断此时的前缀和是否大于k，避免出现int溢出
			if (chalk[i] > k)
			{
				// 直接返回改下标即可
				return i;
			}
		}// 循环后，则表示此时前缀和已经算好了，且不超限
		// 表示k不小于最大前缀和，所以做取余
		k %= chalk[n - 1];

		return binary_search(chalk, k);
		
	}
};


int main()
{
	// 创建类
	Solution s1;

	// 创建数组
	vector<int> chalk;
	
	// 声明字符和整型变量
	char ch;
	int num;
	cin >> ch;
	if (ch == '[')
	{
		while (ch != ']')
		{
			// 每次循环读入一个int整数和一个字符，并判断该字符是否为 ]
			cin >> num >> ch;
			// 将数字压入数组中
			chalk.push_back(num);
		}
	}
	// 声明初始粉笔数，并输入
	int k;
	cin >> k;
	// 用类对象调用函数
	cout << s1.chalkReplacer(chalk, k) << endl;
	

	return 0;
}