网站建设与维护1997年网站没快照
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;
}