abc083d <思维贪心>-526互联

题目

思路

其实全0和全1是无所谓的,只需要全部相同就行了,
因为每次操作是令一个>=k区间的翻转,如果是全1,令[1,n]再翻转一次即可.

考虑[1,i]已经相同,s[i]!=s[i+1]时如何操作,
要使得[1,i+1]相同,要么[1,i]翻转,要么[i+1,n]翻转,
为了使k最大,显然选择大区间翻转,即max(i,n-i),因此ans=min(ans,max(i,n-1)).

总结

划分子问题的思考方式. 进行子问题划分后可能产生分治 - 递归 - 贪心几类算法, 而本题为贪心;
本题贪心的特点是什么? 从左到右考虑问题, 每次产生一个 [i+1, n] 的子问题, 而i处的计算已经通过贪心解决.
经验: 有划分子问题的思维, 按一定顺序思考解决方式(如这里的从左向右), 并假设一部分已经解决(如这里的前i各已经相同)

代码

Code

// https://atcoder.jp/contests/abc083/tasks/arc088_b
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;


void solv()
{
    string s;
    cin >> s;
    int n = s.size();
    int ans = n;
    for (int i = 1; i < n; i ++)
    {
        if (s[i] != s[i-1]) ans = min(ans, max(i, n - i));
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}