题意
给出一个字符串，每次操作可以使得字符串缩短一位，且第$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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607754.html