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 + 10, INF = 1e9 + 10;
int N;
char s[MAXN];
int check(char x) {
    int pre = 0, ans = 0;
    for(int i = 1; i <= N; i++)
        if(s[i] == x) 
            ans = max(ans, i - pre - 1), pre = i;
    return max(ans, N - pre);
}
main() {
    scanf("%s", s + 1);
    N = strlen(s + 1);
    int ans = INF;
    for(char i = 'z'; i >= 'a'; i--) 
        ans = min(ans, check(i));
    printf("%d", ans);
    return 0;
}