题目描述
给定立体区间,进行 m 次空间操作,求第几次操作会出现负数
二分 + 前缀和
利用差分(前缀和)的特性进行区间操作,利用二分的性质找到边界点
Python 代码
import sys
import copy
A, B, C, m = map(int, input().split())
w = list(map(int, sys.stdin.readline().split()))
op = [0] + sys.stdin.readlines()
# 限定 N 大小,会快点儿
N = (A+1)*(B+1)*(C+1)+1
s = [0 for i in range(N)]
b = [0 for i in range(N)]
bp = [0 for i in range(N)]
# d = [
# [0, 0, 0, 1],
# [0, 0, 1, -1],
# [0, 1, 0, -1],
# [0, 1, 1, 1],
# [1, 0, 0, -1],
# [1, 0, 1, 1],
# [1, 1, 0, 1],
# [1, 1, 1, -1]
# ]
get = lambda i,j,k : (i*B+j)*C+k
def check(mid):
b = copy.deepcopy(bp)
# 区间操作引发的差分矩阵变化
for i in range(1, mid+1):
x1, x2, y1, y2, z1, z2, h = map(int, op[i].split())
b[get(x1, y1, z1)] -= h
b[get(x1, y1, z2+1)] += h
b[get(x1, y2+1, z1)] += h
b[get(x1, y2+1, z2+1)] -= h
b[get(x2+1, y1, z1)] += h
b[get(x2+1, y1, z2+1)] -= h
b[get(x2+1, y2+1, z1)] -= h
b[get(x2+1, y2+1, z2+1)] += h
s = [0 for i in range(N)]
# 重新计算前缀和矩阵
for i in range(1, A+1):
for j in range(1, B+1):
for k in range(1, C+1):
s[get(i,j,k)] = b[get(i,j,k)] + s[get(i,j,k-1)]+s[get(i,j-1,k)]+s[get(i-1,j,k)]\
- s[get(i-1,j-1,k)] - s[get(i-1,j,k-1)] - s[get(i,j-1,k-1)]\
+ s[get(i-1,j-1,k-1)]
# 少个循环,会快点儿
# for u in range(1, 8):
# x = i - d[u][0]
# y = j - d[u][1]
# z = k - d[u][2]
# t = d[u][3]
# s[get(i,j,k)] -= s[get(x,y,z)]*t
if s[get(i,j,k)] < 0:
return True
return False
def main():
t = 0
for i in range(1, A+1):
for j in range(1, B+1):
for k in range(1, C+1):
s[get(i, j, k)] = w[t]
t += 1
# 计算差分矩阵
for i in range(1, A+1):
for j in range(1, B+1):
for k in range(1, C+1):
bp[get(i,j,k)] = s[get(i,j,k)] - s[get(i,j,k-1)]-s[get(i,j-1,k)]-s[get(i-1,j,k)]\
+ s[get(i-1,j-1,k)] + s[get(i-1,j,k-1)] + s[get(i,j-1,k-1)]\
- s[get(i-1,j-1,k-1)]
# 少个循环,会快点儿
# for u in range(8):
# x = i - d[u][0]
# y = j - d[u][1]
# z = k - d[u][2]
# t = d[u][3]
# bp[get(i,j,k)] += s[get(x,y,z)]*t
# 操作
l = 1
r = m
while l < r:
mid = l + r >> 1
if check(mid): # 如果是存在负分
r = mid
else:
l = mid + 1
print(l)
if __name__ == "__main__":
main()