座椅搬迁 - 代码源竞赛平台

题目描述

一排有 $n$ 把扶手椅，从左到右编号为 $1$ 到 $n$ 。每把椅子至多坐着一个人，初始坐人的椅子不超过一半。

蜗蜗可以让一个人从当前坐着的椅子 $i$ 移动到一把当前空着的椅子 $j$ ，耗时 $|i-j|$ 分钟。可以进行任意次移动，但移动必须依次完成：上一次移动结束后，才能开始下一次。

目标是让所有最初有人坐着的椅子最终都空出来。中途可以有人移动多次，也可以暂时坐到最初有人坐过的椅子上。求完成目标所需的最少总时间。

第一行包含一个整数 $n$ ，表示椅子数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 。若 $a_i=1$ ，第 $i$ 把椅子最初有人；若 $a_i=0$ ，它最初为空。

输出一行一个整数，表示清空所有初始占用椅子的最少时间。

4
1 0 1 0

2
0 0

样例 1 中，让第 $1$ 把椅子上的人移到第 $2$ 把，再让第 $3$ 把椅子上的人移到第 $4$ 把，耗时 $1+1=2$ 分钟。

样例 2 中没有人坐着，目标一开始就已完成，答案为 $0$ 。

对于 100% 的数据，保证 $2\le n\le 5000$ ， $a_i\in\{0,1\}$ ，且初始坐人的椅子数量不超过 $\lfloor n/2\rfloor$ 。