本文主要是介绍【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(二分、前缀和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!