Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/09/02 08:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串791/1548 (看更多)
還是要多練下二分搜怎麼寫
題目: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]);
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.192.60 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725237918.A.5E2.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 791 之 1548 篇)：