Codeforces Round #719 Arranging The Sheep - 排序

题意

给你一个长度为n的字符串，其中*表示羊，.表示空位。每次只能把羊往左或右移一位，且目标位置得是空位。问最小移几步。

题解

我们首先定义如下数据结构：

static class Sheep {
    int suppose_pos, pos;
}

其中suppose_pos表示这只羊应该在的位置，pos表示这只羊实际的位置。

考虑把所有羊都堆在左边的情况：显然对于第i只羊sheep[i]。有sheep[i].suppose_pos = i；sheep[i].pos等于这只羊在字符串中的下标。且有sheep[i].suppose_pos < sheep[i].pos。

于是对于所有羊都在左边的情况，其结果为：$\sum{pos-suppose\_pos}$。

接下来，我们考虑羊都堆在左边，但在最左边空一格。换句话说，就是从第2个格子开始，把所有羊依次排进去。这里分三种情况：

1. 一开始羊的排列中，第一位本身就没有羊，形如.*..*.*...。相比从第1个格子开始堆羊，每只羊的开销都降低了1。
2. 一开始的排列中，第一位有羊，但第二位没有羊，形如*.**...。相比从第1个格子开始堆羊，右边的羊的开销都降低了1。但是左边的羊需要往右移一位。
3. 一开始的排列中，第一位有羊，第二位也有羊，形如**..*。相比从第1个格子开始堆羊，我们发现前两只羊都需要往右移一步，其余的羊开销减少1。

于是我们发现，当我们移动起始点（记为$start$），往左移往右移取决于$suppose\_pos+start$与$pos$的大小关系。

于是我们对初始的$pos-suppose\_pos$进行排序，并记录下列值：

1. 往右移动的总步数$left\_ans$；
2. 往右移动的羊的数目$count\_left$；
3. 往左移动的总步数$right\_ans$；
4. 往左移动的羊的数目$count\_right$；

当$start=0$时，$left\_ans=0$，$count\_left=0$，$right\_ans=\sum{pos-suppose\_pos}$，$count\_right$等于所有羊的数目。
这样当我们从小往大依次枚举$start$的值的时候，我们能够立刻得出最新的$count\_left$和$count\_right$。接着因为$start$往右移动了一位，因此$left\_ans+=count\_left$，$right\_ans-=count\_right$。于是我们就得到当前$start$的结果为$left\_ans+right\_ans$。

代码