产线切点只能落在相邻元素之间,即班组 b=a[1..i],班组 c=a[i+1..n](1≤i<n)。
预处理前缀和 Si=a1+⋯+ai,以及后缀按位或 Oi=ai∣ai+1∣⋯∣an。枚举切点 i,取 ∣Si−Oi+1∣ 的最小值。
时间复杂度 O(n),空间复杂度 O(n)。
一条产线按顺序处理长度为 n 的整数序列 a。调度要把整条产线从某个相邻位置切开,左边前缀交给班组 b,右边后缀交给班组 c,两段都必须非空。班组 b 的绩效 f 定义为其所负责元素之和,班组 c 的状态码 g 定义为其所负责元素的按位或。财务要对账,希望 ∣f(b)−g(c)∣ 尽可能小。
请枚举所有合法切点,输出该绝对值的最小值。
约束:测试组数 T 满足 1≤T≤102,2≤n≤200000,所有测试中 n 的总和不超过 2000000,0≤ai≤1000000000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册