2019年湘潭大学程序设计竞赛 Black & White （尺取）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<algorithm>
 6 using namespace std;
 7 const int maxn=1e5+10;
 8 int casen;
 9 char s[maxn];
10 int n,m;
11 vector<int>v;
12 int main()
13 {
14     cin>>casen;
15     while(casen--)
16     {
17         v.clear();
18         scanf("%d%d",&n,&m);
19         scanf("%s",s);
20         int sum=0;
21         for(int i=0;i<n;i++)
22         {
23             sum++;
24             if(s[i]!=s[i+1])
25             {
26                 v.push_back(sum);
27                 sum=0;
28             }
29         }
30         //v的作用是将数分开存放 比如0001001在vector中就会存 3 1 2 1 
31         int ans=0;
32         for(int i=0,j;i<v.size();i++)
33         {
34             int mm=m;//mm表示每一次尺取的初始操作数 
35             int tmp=v[i]; //比如还是上面的例子 i=0,tmp为3时 
36             j=i+1;//j是1 表示当前希望将1变成和前面3个相同的数 
37             while(j<v.size()&&mm>=v[j])
38             {
39                 tmp+=v[j];
40                 mm-=v[j];
41                 if(j+1<v.size()) 
42                     tmp+=v[j+1];//再把2加上  
43                 j+=2;
44             }
45             if(j<v.size())//这句话的意思是 如果0011操作一次，应该是3 但是vector中存的是2 2 mm<2,不加这句话答案只能是2 
46                 tmp+=mm;
47             ans=max(ans,tmp);
48         }
49         printf("%d
",ans);
50     }
51 }