https://leetcode.cn/problems/3aqs1c/
这题没有搞出来，但是看题解感觉深受启发：
- 一个是基于DP的实现 https://leetcode.cn/problems/3aqs1c/solution/by-endlesscheng-fu9b/
- 一个是基于超大bits数组的二分实现 https://leetcode.cn/problems/3aqs1c/solution/er-fen-wei-yun-s-by-grby-km9k/ https://codeforces.com/contest/1579/submission/130462038
这里有个等价变化:
- 我们假设 A[i] = sum(x[..i])
- 假设我们测试整体不适宜度是X的话，必须满足
- 那么 max(A[j] - A[i]) <= X.
- 后面定义这个最大最小值的差值为M.
- 也就是说 M <= X
关于这个DP实现解释还比较清楚：
- 可以想象我们从原点出发，每次可以向上走或者是向下走。
- 直觉上可以认为 M <= 2*max(operate)
- 如果可以上下游走的话，可以保证最大值不会超过 max(operate)，最小值不会小于 -max(operate)
- 如果 M <= 2 * max(operate)
- `f[i][j]` 表示考虑前面i个元素之后，和下界距离相差j的时候，min(M)
- 最大下界可以定位为0，最大上界则是 2*max(operate)
- 初始状态下界是0, 并且最大最小差值是0, 所以 f[0][0]=0
class Solution:
def unSuitability(self, operate: List[int]) -> int:
inf = 1 << 30
mx = max(operate) * 2
pre = [inf] * (mx + 1)
pre[0] = 0
for x in operate:
dp = [inf] * (mx + 1)
for off, value in enumerate(pre):
if value == inf: continue
if (off + x) <= mx:
dp[off + x] = min(dp[off + x], max(value, off + x))
if off >= x:
dp[off - x] = min(dp[off - x], value)
else:
dp[0] = min(dp[0], value + x - off)
pre = dp
return min(pre)二分查找方法比较巧妙
- 外层进行二分，假设是检查值是M2
- 初始化B = bits(M2+1, 1)，表示M可以落在里面任何值。
- 注意这里必须使用M2+1来初始化
- 因为表示的范围是是[0, M2], 所以里面有M2+1个bits.
- 对每个元素使用 (B << x) | (B >> x) 模拟M2的变化
- 最终如果B里面包含1的话，那么说明M2是符合条件的。
class Solution:
def unSuitability(self, operate: List[int]) -> int:
low = 1
high = max(operate) * 2
def check(mid):
mask = 2 ** (mid + 1) - 1
t = mask
for x in operate:
t = ((t << x) | (t >> x)) & mask
return t != 0
while low <= high:
mid = (high + low) // 2
ok = check(mid)
if not ok:
low = mid + 1
else:
high = mid - 1
return low