【Codeforces】Vasya and String（二分、前缀和）

本文主要是介绍【Codeforces】Vasya and String（二分、前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

思路：

利用二分搜索和前缀和解决。

AC：

#include<iostream>
#include<algorithm>
using namespace std;
int n, k;
string s;
int sum[100005];
int check(int x)
{for(int i=0 ; i+x<=n ; i++){if (sum[i+x]-sum[i]>=x-k || sum[i + x]-sum[i]<=k)return 1;}return 0;
}
int main()
{cin >> n >> k >> s;sum[0] = 0;for (int i = 0; s[i]; i++){if (s[i] == 'b')sum[i + 1] = sum[i] + 1;elsesum[i + 1] = sum[i];}//二分答案int L = 1, R = n, ans;while (L <= R){int mid = (L + R) / 2;//检查成功，mid可以是答案，继续搜索if (check(mid))ans = mid, L = mid + 1;elseR = mid - 1;}cout << ans << endl;return 0;
}

 

这篇关于【Codeforces】Vasya and String（二分、前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---