Codeforces Round #719 Arranging The Sheep - 排序

题意

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

题解

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

static class Sheep {
    int suppose_pos, pos;
}

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

考虑把所有羊都堆在左边的情况:显然对于第i只羊sheep[i]。有sheep[i].suppose_pos = isheep[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$。

代码

Submission #115300592 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论