Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間4月前 (2025/08/07 00:55)推噓1(1推 0噓 0→)

※ 引述《JIWP (神楽めあ的錢包)》之銘言： : 3479. Fruits Into Baskets III 昨天那題我沒寫這題看完沒什麼想法區間最大區間修改懶得思考就線段樹吧== 不過這題才medium 不知道有沒有更簡單的解法單調什麼之類的看其他人也是用線段樹 class Solution { public: int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) { int n = fruits.size(); int sz = n * 4 + 1; vector<int> tree(sz, 0); // segment_tree for baskets // [1, n] 1-indexed init(tree, 1, 1, n, baskets); int res = 0; for(int i: fruits){ //cout << i << '\n'; if(tree[1] < i) res++; else update(tree, 1, 1, n, i); } return res; } void update(vector<int>& tree, int idx, int l, int r, int i){ if(l == r){ tree[idx] = 0; return; } //cout << idx << ' ' << l << " " << r << '\n'; int m = l + (r - l) / 2; if(tree[idx*2] >= i){ // leftest update(tree, idx*2, l, m, i); } else{ update(tree, idx*2 + 1, m + 1, r, i); } tree[idx] = max(tree[idx*2], tree[idx*2 + 1]); } void init(vector<int>& tree, int idx, int l, int r, vector<int>& baskets){ if(l == r){ tree[idx] = baskets[l-1]; // 0-indexed return; } int m = l + (r - l) / 2; init(tree, idx*2, l, m, baskets); init(tree, idx*2 + 1, m+1, r, baskets); tree[idx] = max(tree[idx*2], tree[idx*2 + 1]); } }; -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg