C. Vasya and String (尺取法)

题目链接：http://codeforces.com/problemset/problem/676/C

题目大意：给你一串字符串(全由 a,b 组成) ，现在你有k次机会可以把a替换成b 或者把b替换成a ，问最长的连续一致的子序列长度

思路：

这道题和 Leetcode 1004 可以说是完全一样了，只是本题既可以替换a 又可以替换b ，那么我们分别考虑两种情况然后求最大就可以了

AC代码：

 1 #include <cstdio>
 2 #include <string>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstdbool>
 6 #include <string.h>
 7 #include <math.h>
 8 
 9 
10 using namespace std;
11 
12 char s[1000005];
13 int k;
14 
15 int change_a(char s[],int len)
16 {
17     int a = 0;
18     int i = 0,j = 0;
19     int sum = 0;
20     while (j<len && i<=j)
21     {
22         if (s[j] == 'a')
23             a++;
24         while (a > k)
25         {
26             if (s[i] == 'a')
27                 a--;
28             i++;
29         }
30         sum = max(sum,j-i+1);
31         j++;
32     }
33     return sum;
34 }
35 
36 int change_b(char s[],int len)
37 {
38     int b = 0;
39     int i = 0,j = 0;
40     int sum = 0;
41     while (j < len && i <= j)
42     {
43         if (s[j] == 'b')
44             b++;
45         while (b>k)
46         {
47             if (s[i] == 'b')
48                 b--;
49             i++;
50         }
51         sum = max(sum,j-i+1);
52         j++;
53     }
54     return sum;
55 }
56 
57 int main()
58 {
59     int len;
60     cin >> len >> k;
61     cin >> s ;
62     int ant = change_b(s,len);
63     int cnt = change_a(s,len);
64     printf("%d
",max(ant,cnt));
65     return 0;
66 }