题目
思路
有两种操作:
- 翻转 这个点。
- 翻转 一个区间。
想要翻转一个不以 为左端点的区间 只需要两步,先翻转,再翻转即可。
因此想到成块的 可以用区间修改,单个的 可以用单点修改。
考虑以下几种情况
00111011
,把中间的零改成 再区间修改需要 次操作,优于两次区间修改。001110011
,把中间两个零改成 再区间修改需要 次操作,和两次区间操作相同。00111010
,把中间的零改成 再区间修改需要 次操作,和一次区间修改加一次单点修改相同。001110010
,把中间的两个零改成 再区间修改需要 次操作,劣于一次区间修改加一次单点修改。
从以上四种情况总结出先把单个的 都改成 如果最后有两个 的块(长度大于 ,且都是 ) 中间只有一个零就可以先把零改成 再区间修改了。
Code
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #define MAXN 100001 int n, ans, a[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= n; ++i) { if (a[i] == 1 && i != 1 && a[i - 1] == 0 && a[i + 1] == 0) { ++ans; a[i] = 0; } if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) { a[i] = 1; ++ans; } } int last = 0; for (int i = 1; i <= n; ++i) { if (last == 0 && a[i] == 1) { last = i; } if (last != 0 && a[i] ==0) { if (last == 1) ++ans; else ans += 2; last = 0; } } if (last != 0) { if (last == 1) ++ans; else ans += 2; last = 0; } std::cout << ans << '\n'; return 0; }