约瑟夫环：

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {

        int n=chalk.size(),i=-1;
        long long sum=0;
        for(int j=0;j<n;j++)
            sum+=chalk[j];
        k%=sum;
        while(1){
            i=(i+1)%n;
            if(k<chalk[i]){
                return i;
            }else{
                k-=chalk[i];
            }
        }
        
        return 0;
    }
};

前缀和+二分：

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:
    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%=chalk[n-1];

        //二分查找
        int i=0,j=n-1;
        while(i<=j){
            int mid=(i+j)/2;
            if(chalk[mid]>k){
                j=mid-1;
            }else if(chalk[mid]<=k){
                i=mid+1;
            }
        }
        return i;
       // return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
    }
};