鏈接：https://ac.nowcoder.com/acm/contest/893/F
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld
題目描述
你有一個(gè)長(zhǎng)度為 n 的 01 串S，你可以執(zhí)行最多 m 次操作。
對(duì)于每次操作，你可以選擇一個(gè)位置 i 滿足 1 \le i \le n1≤i≤n，翻轉(zhuǎn)這一位的值，0變成1，1變成0。
定義一個(gè) 01 串的價(jià)值為其中最長(zhǎng)連續(xù)0的個(gè)數(shù)和最長(zhǎng)連續(xù)1的個(gè)數(shù)的較大值，求S在經(jīng)過最多m次操作后的最大價(jià)值。
輸入描述:

• 第一行一個(gè)整數(shù) T ，表示接下來有 T 個(gè)樣例。
• 首先輸入n,m，表示S串的長(zhǎng)度n和操作次數(shù)m，其中1 \le n \le 1000001≤n≤100000，0 \le m \le 10000≤m≤1000；
• 接下來輸入一個(gè)長(zhǎng)度為n的字符串S。
  輸出描述:
  一個(gè)整數(shù)，表示題面上描述的最大價(jià)值。
  示例1
  輸入
  復(fù)制

25 1001012 101

輸出
復(fù)制

4 2

說明
第一個(gè)串翻轉(zhuǎn)第三個(gè)位置，00001的價(jià)值為4；第二個(gè)串翻轉(zhuǎn)第一個(gè)位置，11的價(jià)值為2。

#include <bits/stdc++.h> using namespace std; int n,m; string s; int solve(char c) {int cnt = 0,ans = 0,L = 0;for(int i = 0; i < n; i++){if(s[i] == c) cnt++;//要修改的個(gè)數(shù)if(cnt > m) ans = max(ans,i-L);while(cnt > m)//要修改的個(gè)數(shù)大于m，L要右移{cnt -= (s[L++] ==c);}ans = max(ans,i-L+1);}s.clear();return ans; } int main() {int t;cin>>t;while(t--){cin>>n>>m;cin>>s;int res = max(solve('0'),solve('1'));cout<<res<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2019年湘潭大学程序设计竞赛（重现赛）补题：F.Black White(尺取法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。