ZJUT 1703
Position Arrangement
题目地址：
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1703
应谷种同学所发的链接。于是做了一下这道题。不过复习期间忙于数电、自控的复习。某天晚上写了下想法，今天下午写的代码。
一开始是想着找出最多的连续的“1”，然后所有数往这堆连续的“1”靠，不过由于算法基础潺弱，要找这个估计是用最笨的办法，可能早就超时了。
后来想到数据结构与算法分析里的一道题。总之就是第一步先找基准点，第二步再把所有其他的数都往这个基准上靠。
但实际想的过程是相反的。基本上是完全逆向倒推的。首先是最后还剩一个点的时候，必然是这个点往已经集结在一起的“1”靠。再倒推，可知这即是离散的点都往基准点靠。
离散的点比较好办。而本来是一堆的点就比较难办，因为不确定是哪一“堆”往哪一“堆”移动。
假想了以下的场景：
（1）两堆“1”的数量相同，即对称分布，例如00111001110等。这种情况无论是左堆往右堆移，还是反之，亦或是两堆都往中间移，都是一样的。
（2）两堆“1”的数量不同，即非对称分布，例如00110011110，01100111100等。这种情况，则必须是左堆往右堆移。
从另一个角度来看，在最靠两边的两个“1”，即最左/最右的“1”，不可能往左/往右移，只有往右/往左移，或者原地不动；依次类推，左边第2个和右边第2个也是只有往右/往左移或者原地不动。那边到最中间的情况，有可能有两种情况，一种是字符串中有奇数个“1”，则那个在最中间的"1"就是原地不动的，而其他的“1”则向这个中心“1”靠拢。那么这个“1”就是基准点。另一种情况，是有偶数个"1"，那么则是左边的所有“1”向中间偏左的“1”靠，右边的也是这样。那么这中间的两个“1”共同构成一个基准，在左右的1都靠到中间这两个半中心“1”后，则到了上面所说的场景（1），即是左半的所有1（包括作为半中心的“1”）往右移一段距离，这段距离是两个半中心“1”间的距离。这样，就找到了基准点。
如上所述，则移动的步骤就是如此。
实际编码，则是用两个数组，一个数组存储input的字符串，另一个数组存储input的字符串中的1出现的位置。然后用ix_mid_prev,ix_mid_next,ix_mid_left,ix_mid_right来存储“下一步移动的1所要到达的位置的旁边的1所在的位置”，并在移动过程中用上述的变量与pos_one中的数（即1未移动时所在的位置）相减，得到移动的步数。
diff则是表示偶数个1中，两个半中心1间的距离。
done
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100002
#define ORDER_MAX 100000
int mov_cnt(char *, int);
int main(void)
{
char str[MAX];
int res[ORDER_MAX];
int i;
int status;
for (i = 0; i < ORDER_MAX; ++i)
{
status = scanf("%s", str);
if (-1 == status)
break;
res[i] = mov_cnt(str, strlen(str));
printf("Case #%d: %d\n", (i+1), res[i]);
}
return 0;
}
int mov_cnt(char *str, int arr_width)
{
int pos_one[arr_width];
int mid, mid_prev, mid_next, ix_mid;
int /*mid_left, mid_right, */diff;
int ix_mid_left, ix_mid_right;
/* int pos_cnt_prev, pos_cnt_next;*/
int pos_cnt = 0;
int cnt_mov = 0;
int pos;
/*first step: find all the postion of '1'*/
for ( pos = 0; pos < arr_width; ++pos)
{
if ('1' == str[pos])
{
pos_one[pos_cnt] = pos;
pos_cnt++;
}
}
/*second step: locate the middle postion of '1'*/
if (pos_cnt % 2) /*the total '1' is odd*/
{
ix_mid = (pos_cnt/2);
mid = pos_one[ix_mid];
/*third step(1):*/
/*left side*/
mid_prev = mid;
for (; ix_mid >= 0; ix_mid--)
{
cnt_mov += mid_prev - pos_one[ix_mid];
mid_prev--;
}
/*right side*/
mid_next = mid;
for (ix_mid = (pos_cnt/2); ix_mid < pos_cnt; ix_mid++)
{
cnt_mov += pos_one[ix_mid] - mid_next;
mid_next++;
}
}
else /*the total '1' is even*/
{
ix_mid_left = pos_cnt/2 - 1;
ix_mid_right = ix_mid_left + 1;
/*third step(2)*/
diff = pos_one[ix_mid_right] - pos_one[ix_mid_left] - 1;
/*left side*/
mid_prev = pos_one[ix_mid_left];
for (; ix_mid_left >= 0; ix_mid_left--)
{
cnt_mov += mid_prev - pos_one[ix_mid_left];
mid_prev--;
}
/*right side*/
mid_next = pos_one[ix_mid_right];
for (; ix_mid_right < pos_cnt; ix_mid_right++)
{
cnt_mov += pos_one[ix_mid_right] - mid_next;
mid_next++;
}
cnt_mov += (pos_cnt/2)*diff;
}
return cnt_mov;
}