网站名称填写什么,深圳高端设计公司名单,php视频转码,怎么用wordpress做模板C - 烟销日出不见人 问题陈述
给定一个长度为 NN 的字符串 SS#xff0c;由 0 和 1 组成。保证 SS 至少包含一个 1。
您可以执行以下操作任意次数#xff08;可能为零#xff09;#xff1a;
选择一个整数 ii (1≤i≤N−11≤i≤N−1)#xff0c;并交换 SS 的第 ii 个和…
C - 烟销日出不见人 问题陈述
给定一个长度为 NN 的字符串 SS由 0 和 1 组成。保证 SS 至少包含一个 1。
您可以执行以下操作任意次数可能为零
选择一个整数 ii (1≤i≤N−11≤i≤N−1)并交换 SS 的第 ii 个和第 (i1)(i1) 个字符。
找出使所有 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×105NN 是一个整数。SS 是一个长度为 NN 的字符串由 0 和 1 组成。SS 至少包含一个 1。
输入
输入通过标准输入以以下格式给出
NN
SS输出
打印答案。
示例 1
InputcopyOutputcopy 7
01010013例如以下三个操作使所有 1 连续
选择 i2i2 并交换第 2 个和第 3 个字符。然后SS 0011001。选择 i6i6 并交换第 6 个和第 7 个字符。然后SS 0011010。选择 i5i5 并交换第 5 个和第 6 个字符。然后SS 0011100。
不可能在两次或更少的交换中做到这一点因此答案是 33。
示例 2
InputcopyOutputcopy 3
1000所有 1 已经是连续的因此不需要交换。
示例 3
InputcopyOutputcopy 10
01010010017
思路
假设最左端在第一个点移动次数最小 然后从此点循环到最右点-1的个数点 每循环一次看有多少点应该向右移有多少点应该向左移但他们都向左移动了所以要计算
代码
//假设最左端在第一个点移动次数最小
//然后从此点循环到最右点-1的个数点
// 每循环一次看有多少点应该向右移有多少点应该向左移但他们都向左移动了所以要计算
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
char a[600010];
int b[600010];
int n;
long long sum 0, max 0, h 0, q, i, zong 0,y0;
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] 1h0) {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 q1;i b[y-1] - h1 zongy;i) {while (izong b[zong]zongy ) {zong;}//有几个要向右移动max max 2 * zong - h;//zong个要向右移动h-zong个不要向右移动但移动了减去sum sum max ? sum : max;}printf(%lld\n, sum);return 0;
}
