※ 引述《enmeitiryous (enmeitiryous)》之铭言：
: 还是要多练下二分搜怎么写
: 题目:1894. Find the Student that Will Replace the Chalk
: 给你一个vector chalk, chalk[i]代表第i个学生要花费的chalk，给你一个数字k求当学
: 生轮流花费chalk[i]直到k被花光是第几号位学生(到第n-1号学生若k没花完则跳回0号
: 思路:一开始想说试下模拟解，但k会到10**9所以是不行的，第二个想到应该是先求出
: prefixsum后，用二分搜找出会落在哪，而轮流这件事可以用k%presum[n-1]解决
: int bs(vector<long long int>& pre_ans,long long int tar){
: int left=0;
: int right=pre_ans.size()-1;
: int mid;
: while(left<right){
: mid=left+(right-left)/2;
: if(pre_ans[mid]<=tar){
: left=mid+1;
: }
: else{
: right=mid;
: }
: }
: return right;
: }
: int chalkReplacer(vector<int>& chalk, int k) {
: int cring=0;
: int n=chalk.size();
: vector<long long int> pre_ans(n,0);
: pre_ans[0]=chalk[0];
: for(int i=1;i<n;++i){
: pre_ans[i]=pre_ans[i-1]+chalk[i];
: }
: if(pre_ans[n-1]>k){
: return bs(pre_ans,k);
: }
: else{
: return bs(pre_ans,k%pre_ans[n-1]);
: }
: }
思路:
虾鸡巴写 本来想暴力解 TLE修一下就变这样了
应该能再优化 但我懒得想了
Python Code:
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
n = sum(chalk)
q = k // n
k -= n * (q - 1)
while k > 0:
for i in range(len(chalk)):
if k - chalk[i] < 0:
return i
elif k - chalk[i] == 0:
if i + 1 < len(chalk):
return i + 1
else:
return 0
else:
k -= chalk[i]