当前位置： 移动技术网 > IT编程>开发语言>C/C++ > agc016A - Shrinking(字符串 贪心)

agc016A - Shrinking(字符串 贪心)

2018年09月21日  | 移动技术网IT编程  | 我要评论

瑜伽用品,lol风云直播间,博鳌论坛2013

题意

给出一个字符串，每次操作可以使得字符串缩短一位，且第$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;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网