[算法训练] 513周赛-①Q3-二分+前缀和Q2/Q4-树状数组+逆序对
899 字
4 分钟
[算法训练] 513周赛-①Q3-二分+前缀和Q2/Q4-树状数组+逆序对
513周赛-①Q3-二分+前缀和Q2\Q4-树状数组+逆序对
🏆 第 513 场力扣周赛 - 讨论 - 力扣（LeetCode）
Q3-二分+前缀和
题目
给你两个整数数组 tasks 和 shifts。
tasks[i]表示完成第ith个任务所需的时间。shifts[j]表示第jth个班次可用的时间。
任务必须 按照从左到右的顺序处理。
- 延续处理： 如果一个任务在当前班次内没有完成，则下一班次会从该任务的 相同进度位置 继续处理。
- 重新开始： 如果一个班次内完成了所有任务，则该班次会 立即结束 。该班次剩余的时间会被 丢弃，下一班次会重新从第 0 个任务开始。
如果一个任务尚未被完全完成，则认为该任务是未完成 的。这包括当前正在执行中的任务。
返回一个整数数组 ans，其中 ans[j] 表示第 jth 个班次结束后剩余的未完成 任务数量。
模拟
class Solution: def countTasks(self, a: List[int], b: List[int]) -> List[int]: n = len(a) m = len(b) ans = [] idx = 0 rem = a[0] tot = sum(a) for t in b: if idx == 0 and t >= tot: ans.append(0) idx = 0 rem = a[0] continue while t > 0 and idx < n: if t >= rem: t -= rem idx += 1 if idx < n: rem = a[idx] else: rem -= t t = 0 ans.append(n - idx) if idx == n: idx = 0 rem = a[0] return ans二分+前缀和
例如 tasks=[2,3,4]，其前缀和数组为 s=[2,5,9]。
由于 tasks 中的数都是非负数，所以 s 是递增的。我们可以在有序数组 s 中二分查找最后一个 ≤t 的数的下标 k，那么已完成的任务下标为 [0,k]，未完成的任务下标为 [k+1,n−1]，这有 n−k−1 个。
class Solution: def countTasks(self, tasks: list[int], shifts: list[int]) -> list[int]: n = len(tasks) for i in range(1, n): tasks[i] += tasks[i - 1] t = 0 for i, shift in enumerate(shifts): t += shift if t >= tasks[-1]: t = 0 shifts[i] = 0 else: shifts[i] = n - bisect_right(tasks, t) return shiftsQ2/Q4-树状数组
题目
给你一个整数数组 nums，以及两个整数 a 和 b。
对于一个 子数组 ，定义：
x表示其中偶数元素的数量。y表示其中奇数元素的数量。
子数组中偶数与奇数的比例定义为 x / y，其中该比例按照精确的有理数值进行比较。
如果一个子数组满足以下条件，则称其为 有效子数组 ：
y > 0，并且x / y <= a / b。
返回 nums 中有效子数组的数量。
子数组是数组中一个连续的非空 元素序列。
树状数组+逆序对
x / y <= a / b 等价于ay - bx ≥ 0
将数组中的奇数视作a，偶数视作-b得到新数组arr
问题等价于：arr中有多少个元素和 ≥0 的非空连续子数组
arr的子数组[L,R-1]的元素和等于s[R] - s[L]，问题等价于：
有多少个下标对 (L,R) 满足 0≤L<R≤n 且 s[R]−s[L]≥0
枚举 R，我们需要知道在 R 的左边有多少个 s[L]≤s[R]
class Fenwick: def __init__(self, n): self.n = n self.bit = [0] * (n + 1) def add(self, idx, val): idx += 1 while idx <= self.n: self.bit[idx] += val idx += idx & -idx def sum(self, idx): idx += 1 res = 0 while idx > 0: res += self.bit[idx] idx -= idx & -idx return resclass Solution: def countRatioSubarrays(self, nums: list[int], a: int, b: int) -> int: n = len(nums) pre = [0] for v in nums: if v % 2 == 0: pre.append(pre[-1] + b) else: pre.append(pre[-1] - a) ans = 0 val = sorted(set(pre)) rank = {v:i for i,v in enumerate(val)} bit = Fenwick(len(val)) for i,p in enumerate(pre): r = rank[p] ans += i - bit.sum(r-1) bit.add(r,1) return ans文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
[算法训练] 513周赛-①Q3-二分+前缀和Q2/Q4-树状数组+逆序对
http://blog.7a7a68.xyz/posts/513周赛/ 相关文章 智能推荐
1
[算法训练] 514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树
算法训练 LeetCode514周赛
2
[算法训练] 509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher
算法训练 LeetCode509周赛
3
[算法训练] 512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学
算法训练 LeetCode512周赛
4
[算法训练] 186双周赛-①Q1-枚举②Q2-贪心/状态机DP③前缀和优化DP
算法训练 LeetCode186双周赛
5
[算法训练] 507周赛-①贪心②前缀和+暴力枚举/前缀和+三指针滑动窗口③分层图最短路④二分答案
算法训练 LeetCode507周赛
随机文章 随机推荐