网站目标定位概念品牌营销的概念
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;
}