文章目录

CSES 2425 Stack Weights 做题笔记

发布于

题意

有 $n$ 个砝码,编号为 $1$ 到 $n$。编号大的砝码一定比编号小的砝码重。

做 $n$ 操作,每次操作是把某个还没放在天平上的砝码放到天平的左边或者右边。问能否确定天平两边重量关系。

题解

定义 $l_i$ 为天平左边中,编号大于等于 $i$ 的砝码个数,$r_i$ 为天平右边中,编号大于等于 $i$ 的砝码个数。

左边比右边重,当且仅当对于所有 $1 \leq i \leq n$,满足 $l_i \geq r_i$。

原因很简单。若存在 $k$ 使得 $l_k < r_k$,则将编号小于 $k$ 的砝码 $i$ 的重量都定为 $i$,编号大于等于 $k$ 的砝码 $i$ 的重量都定为极大值加上 $i$ 即可使左边更轻。

用树状数组维护 $l_i - r_i$ 的值即可。


暂无评论

发表评论