Swap to Gather-----

C - 烟销日出不见人

 

问题陈述

给定一个长度为 NN 的字符串 SS，由 0 和 1 组成。保证 SS 至少包含一个 1。

您可以执行以下操作任意次数（可能为零）：

• 选择一个整数 ii (1≤i≤N−11≤i≤N−1)，并交换 SS 的第 ii 个和第 (i+1)(i+1) 个字符。

找出使所有 1 连续所需的最小操作次数。

在这里，只有当存在整数 ll 和 rr (1≤l≤r≤N1≤l≤r≤N) 时，所有 1 被称为连续，且 ii 的第 1 个字符为 SS 当且仅当 l≤i≤rl≤i≤r，否则为 0。

约束条件

• 2≤N≤5×1052≤N≤5×105
• NN 是一个整数。
• SS 是一个长度为 NN 的字符串，由 0 和 1 组成。
• SS 至少包含一个 1。

输入

输入通过标准输入以以下格式给出：

NN
SS

输出

打印答案。

示例 1

Inputcopy	Outputcopy
7 0101001	3

例如，以下三个操作使所有 1 连续：

• 选择 i=2i=2 并交换第 2 个和第 3 个字符。然后，S=S= 0011001。
• 选择 i=6i=6 并交换第 6 个和第 7 个字符。然后，S=S= 0011010。
• 选择 i=5i=5 并交换第 5 个和第 6 个字符。然后，S=S= 0011100。

不可能在两次或更少的交换中做到这一点，因此答案是 33。

示例 2

Inputcopy	Outputcopy
3 100	0

所有 1 已经是连续的，因此不需要交换。

示例 3

Inputcopy	Outputcopy
10 0101001001	7

思路： 

假设最左端在第一个点，移动次数最小；
然后从此点循环到最右点-1的个数点，
 每循环一次看有多少点应该向右移，有多少点应该向左移，但他们都向左移动了，所以要计算

代码：

//假设最左端在第一个点，移动次数最小；
//然后从此点循环到最右点-1的个数点，
// 每循环一次看有多少点应该向右移，有多少点应该向左移，但他们都向左移动了，所以要计算
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
char a[600010];
int b[600010];
int  n;
long long sum = 0, max = 0, h = 0, q, i, zong = 0,y=0;
int main() {scanf("%d", &n);for ( i = 0;i < n;i++) {do{scanf("%c", &a[i]);} while (a[i] != '1' && a[i] != '0');}for ( i = 0;i < n;i++) {if (a[i] == '1'&&h==0) {q = i;b[y++] = i;max += i -q -h;h++;}//第一个点else if (a[i] == '1') {b[y++] = i;max+= i -q -h;h++;}//后面的点到据第一个点的h距离}sum = max;for ( i = q+1;i <= b[y-1] - h+1 && zong<y;i++) {while (i+zong >b[zong]&&zong<y ) {zong++;}//有几个要向右移动max = max + 2 * zong - h;//zong个要向右移动，h-zong个不要向右移动但移动了（减去）sum = sum < max ? sum : max;}printf("%lld\n", sum);return 0;
}