Codeforces Round #719 Arranging The Sheep - Sort

Solution:

We define the data structure below:

static class Sheep {
    int suppose_pos, pos;
}

suppose_pos represent the position of this supposed to be. pos represent the actual position of this sheep (the index in the string).

Let consider all sheep are lined up to the very left:
For i-th sheep sheep[i]. So, we have sheep[i].suppose_pos = i；sheep[i].pos is equal to the index of this sheep in the string. And of course, sheep[i].suppose_pos < sheep[i].pos.

So, for the case we lined up to the very left, the total cost is: $\sum{pos-suppose\_pos}$.

The we consider all sheep are lined up to very left but except for 1 cell. In other words, all sheep are lined up start from 2nd cell. There are three cases:

1. There is no sheep on the first cell. Like .*..*.*.... Compare to start from first cell, all the cost reduced 1.
2. There is a sheep on the first cell. But not sheep on second cell. Like *.**.... Compare to start from first cell, the cost of sheep on the right reduced 1. But the first sheep need move to right.
3. Both first cell and second cell have sheep. Like **..*. Compare to start from first cell, the first two sheep need move to right. The cost of other sheep reduced 1.

Now we found that when we move the start point of the line (denoted by $start$), the number of sheep which move to left/right is depends on the The relationship between $suppose_pos+start$ and $pos$.

So, we sort all sheep by $pos-suppose\_pos$. And note down the following values:

1. The total cost of move from left to right. Denoted by $left\_ans$;
2. The number of sheep which move from left to right. Denoted by $count\_left$;
3. The total cost of move from right to left. Denoted by $right\_ans$;
4. The number of sheep which move from right to left. Denoted by $count\_right$;

When $start=0$, $left\_ans=0$, $count\_left=0$, $right\_ans=\sum{pos-suppose\_pos}$, $count\_right$ equals the total number of sheep.
So, when we enumerate the values of $start$ from small to large, we can calculate the latest $count\_left$ and $count\_right$.
Because we move one more step right for $start$. So, $left\_ans+=count\_left$, $right\_ans-=count\_right$. Which means all the sheep move from left to right need one more step. And the sheep move from right to left can save one more step.
Then we know, for current $start$, the cost is  $left\_ans+right\_ans$

Code: