皮老师的烟火

\\n\\n## 题目背景\\n\\n2025 年的最后一晚，长街两侧挂满红灯笼，烟花仓库排成一条直线，编号为 $1\\\\sim N$。为了让 **0 点整** 的烟火恰好在每个仓库“对齐到指定亮度”，皮老师创办的幽灵物流工会启用了他们的秘密装置：**后缀传导器**。\\n\\n每一支小队会在某个起点注入一股能量，让它一路传导到街尾；同时还会在某个位置放置“反向抵消器”，把后续的传导抹掉。 \\n\\n由于设备来自“跨年夜的缝隙”，抵消器甚至可能出现在注入点之前 —— 这会让某一段街区出现“反向修正”。\\n\\n工会还提出了“新年均衡化”口号：不只要能做出来，还要让 **最累的人别太累**。\\n\\n## 题目描述\\n\\n给定整数 $N$ 和目标数组 $B_1,B_2,\\\\dots,B_N$。初始时数组 $A$ 全为 $0$。\\n\\n你需要进行 **恰好 $N$ 次操作**。第 $i$ 次操作给定两个整数 $L_i,R_i$，并且你需要为它选择一个整数权值 $w_i$（可为负数）。该操作对数组 $A$ 的影响定义为：\\n\\n- 对所有 $j\\\\in[L_i,N]$，令 $A_j \\\\leftarrow A_j + w_i$；\\n \\n- 对所有 $j\\\\in[R_i+1,N]$，令 $A_j \\\\leftarrow A_j - w_i$（若 $R_i=N$，这一条为空操作）。\\n \\n\\n输入保证：$\\\\{L_1,L_2,\\\\dots,L_N\\\\}$ 是 $1\\\\sim N$ 的一个排列（每个位置恰好作为一次操作的注入点）。\\n\\n你的目标是让最终 $A_i = B_i$（对所有 $1\\\\le i\\\\le N$）成立，并在所有可行方案中做如下双目标优化（按优先级从高到低）：\\n\\n1. **最小化最大单次负荷**\\n \\n $$\\n K = \\\\max_{1\\\\le i\\\\le N} |w_i|\\n $$\\n \\n2. 在满足 $K$ 最小的前提下，**最小化总负荷**\\n \\n $$\\n S = \\\\sum_{i=1}^{N} |w_i|\\n $$\\n \\n\\n请输出最小的 $K$ 以及在该 $K$ 下对应的最小 $S$。若无解输出 $-1$。\\n\\n## 输入格式\\n\\n第一行一个整数 $N$。\\n\\n第二行 $N$ 个整数 $B_1,B_2,\\\\dots,B_N$。\\n\\n接下来 $N$ 行，每行两个整数 $L_i,R_i$。\\n\\n## 输出格式\\n\\n若无解，输出一行 `-1`。 \\n否则输出一行两个整数：最小的 $K$ 与对应最小的 $S$。\\n\\n\\n```input1\\n6\\n2 0 -2 0 0 1\\n1 6\\n2 3\\n3 5\\n4 1\\n5 6\\n6 6\\n```\\n\\n```output1\\n2 7\\n```\\n\\n## 数据范围\\n\\n对于 $20\\\\%$ 的数据，满足 $1 \\\\le N \\\\le 500$\\n \\n对于另 $30\\\\%$ 的数据，满足 $1 \\\\le N \\\\le 2\\\\times 10^5$，且额外保证 $L_i \\\\le R_i$。\\n\\n对于 $100\\\\%$ 的数据，满足：\\n- $1 \\\\le N \\\\le 2\\\\times 10^5$\\n- $|B_i| \\\\le 10^9$\\n- $1 \\\\le L_i \\\\le N,\\\\ 1 \\\\le R_i \\\\le N$\\n- $\\\\{L_i\\\\}$ 为 $1\\\\sim N$ 的排列。\

统计

递交统计

皮老师的烟火

信息

还没有账户？

登录