※ 引述《sustainer123 (caster )》之銘言：
: ※ 引述《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]
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725325756.A.335.html
推 sustainer123: 我感覺今天比昨天難 09/03 09:09
補了一下昨天的題目
先 % 取餘數
再逐個扣掉
Python Code:
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
k %= sum(chalk)
for i, c in enumerate(chalk):
if k >= c:
k -= c
else:
return i
早知道昨天就寫了 哀哀哀