本文共 1268 字，大约阅读时间需要 4 分钟。

魔法石

时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] 题目描述 你习得了魔法，并学会了熟练运用魔法石。 你得到了n颗魔法石，魔法石有两种属性，分别为火属性和水属性。你一开始得到的是这n颗魔法石的一个排列。定义这n颗魔法石释放出来的能量，为最长的属性相同的魔法石连续段的长度。 作为一名熟练的魔法师，你还可以至多修改k个魔法石的属性。你现在想知道这n颗魔法石最多可以释放出多少能量。 输入 第一行为两个正整数n,k，表示魔法石的个数和最多可以修改的魔法石数量。 接下来一行为一个长度为n的字符串，第i个字符表示第i颗魔法石的属性，a为火属性，b为水属性。 输出 输出为一行一个正整数，表示这n颗魔法石最多可以释放出的能量大小。 样例输入 Copy 【样例1】 4 2 abba 【样例2】 8 1 aabaabaa 样例输出 Copy 【样例1】 4 【样例2】 5 提示 对于30%的数据，满足n≤20。 对于60%的数据，满足n≤1000。 对于另外20%的数据，满足所有魔法石属性均相同。 对于100%的数据，满足1≤k≤n≤105。

cf原题翻译版。。

题意就是让你找到修改k个属性后，最长同属性的魔法石长度。

数据很大，用尺取就可很好的解决，做的尺取也不是很多，寻思半天，我太vegetable了。 显然有两种情况，一个是改成 a ，一个是改成 b。说下改成 a 的情况，首先模拟一个队列，从头开始往队列里面放元素，是 a 的话直接放进去，是 b 的话判断是否有可用的操作改成 a ，有的话直接把 b 放进去，没有的话需要从队头开始去掉 a ，一直去到出现 b 为止，让后每次更新答案即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105959159 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！