[cf] Codeforces Round #789 (Div. 2)

前言

传送门:

B2.

t a g : tag : tag:贪心 分治 字符串 给你一串 01 01 01 字符串,询问将其变为 g o o d good good的最小操作次数和最终状态的最小段数

操作 : 将 1 1 1变为 0 0 0,将 0 0 0变为 1 1 1

g o o d : good : good: 当且仅当连续的 11... 11... 11..., 00.. 00.. 00..个数都为偶数的时候

思路 : 因为最终状态是 偶数

所以必然存在 s [ i ] = s [ i + 1 ] s[i]=s[i+1] s[i]=s[i+1],因此对于 s [ i ] ≠ s [ i + 1 ] s[i]\neq s[i+1] s[i]​=s[i+1]的位置,我们必然需要掏出一个操作

那么怎么考虑最小段数呢 ?

显然对于原有的 00 , 11 00,11 00,11这种组合我们是不需要进行拆分的

因此我们只需要考虑 01 , 10 01,10 01,10,那么我们遇到 01 , 10 01,10 01,10这种组合的时候是把它变为 00 00 00还是 11 11 11呢

我们贪心的考虑将其放入最近的分组里面

最后判断答案,发现正确

code :

void solve(){
	int n;cin>>n;
	string s;cin>>s;
	
	int ans = 0 ;
	int cnt = 0 ;
	int pre = -1;
	
	for(int i=0;i