题目传送门:Problem - C - Codeforces
题目大意
有多组测试用例。
给定一个01字符串S,从前往后删除若干字符,从后往前删除若干字符,留下中间连续的一串字符,不同的方案的代价为max(删除的1的个数,留下的0的个数),问最小的代价是多少?
思路(双指针 + 贪心)
会留下中间一段,所以可以用双指针来表示中间这一段,枚举左端点,然后贪心,复杂度为O(N)。
贪心的原理为:当留下的0和删除的1相等的时候,就不要再往右扩大了,因为再向右扩大留下区间范围的话,留下的0只会增加,删除的1只会减少,这样只会让代价更大。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9, inf = 8e18; char s[maxn]; void solve() { cin >> s + 1; int N = strlen(s + 1); int removed_1 = 0, left_0 = 0, ans = inf; for(int i = 1;i <= N; ++ i)if(s[i] == '1')removed_1 ++; for(int i = 1, j = 0;i <= N; ++ i) { while(j < N && left_0 < removed_1) { ++ j; if(s[j] == '0')left_0 ++; else removed_1 --; ans = min(ans, max(removed_1, left_0)); } if(s[i] == '0')left_0 --; else removed_1 ++; ans = min(ans, max(left_0, removed_1)); } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(0); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING