商品交换电子商务网站开发/一个产品的网络营销方案

题解 

题目比较简单   每个人轮流   直到k减为负数

普通方法   先求所有学生需要的粉笔数量   k%总数  就是最后一轮的粉笔数量   最后遍历减一遍就能算出答案 注意前面求需要粉笔总数的时候开long long型

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

前缀和+二分查找

思路和前面的类似  只是前面求和 这边求前缀和  方便下一步遍历 只需要二分就行 不需要顺序查找

class Solution {
public:int bin_search(int left, int right, int target, const vector<int> &chalk) {while(left <= right) {int mid = (left + right) / 2;if(chalk[mid] > target) right = mid - 1;else left = mid+1;}return left;}int chalkReplacer(vector<int>& chalk, int k) {int n = chalk.size();if (chalk[0] > k) return 0;for(int i=1; i<n; i++) {chalk[i] += chalk[i-1];if (chalk[i] > k) return i;}k = k % chalk[n-1];return bin_search(0, n-1, k, chalk);}
};