agc016A - Shrinking(字符串贪心)

题意

题目链接

给出一个字符串，每次操作可以使得字符串缩短一位，且第$i$位必须要保证与变换前的这一位或下一位相同，

问使得整个字符串全相同最少的操作次数

Sol

300P的题我都要想10min啊，还是太菜了。。

首先我们可以枚举一个字母，强行让他成为最后的答案

对于末尾与它不同的数只能一个个删掉，而中间的数需要从下一个与它相同的一个个传递而来

取一下max即可

所以，，我们就用一个$O(26n)$的算法A掉了一个$n \leqslant 100$的题？？？？

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 1e6 + , INF = 1e9 + ;

int N;

char s[MAXN];

int check(char x) {

    int pre = , ans = ;

    for(int i = ; i <= N; i++)

        if(s[i] == x)

            ans = max(ans, i - pre - ), pre = i;

    return max(ans, N - pre);

}

main() {

    scanf("%s", s + );

    N = strlen(s + );

    int ans = INF;

    for(char i = 'z'; i >= 'a'; i--)

        ans = min(ans, check(i));

    printf("%d", ans);

    return ;

}

巴特西

agc016A - Shrinking(字符串贪心)

题意

Sol

最新文章

热门文章

巴特西

agc016A - Shrinking(字符串 贪心)

题意

Sol

最新文章

热门文章

agc016A - Shrinking(字符串贪心)