【2023暑假专题测试1】最长的Y

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200000;
const int INF = 1'000'000'000'000'000'000LL;
string s;
int k, n;
// allY[0] 存数量
int allY[MAXN + 5];
int sum[MAXN + 5]; // allY 的前缀和
// 首项为 x 末项为 y 的等差数列求和
int cal(int x, int y)
{
    return (x + y) * (y - x + 1) / 2;
}
// 检查 len 长度的 y 能不能达成
bool check(int len)
{
    int cnt = INF;
    for (int l = 1; l + len - 1 <= allY[0]; l++)
    {
        int r = l + len - 1;
        int mid = (l + r) / 2;
        int now = 0;
        now += (sum[r] - sum[mid - 1]) -
               cal(allY[mid], allY[mid] + r - mid);
        now += cal(allY[mid] - (mid - l), allY[mid]) -
               (sum[mid] - sum[l - 1]);
        cnt = min(cnt, now);
    }
    return cnt <= k;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> k;
    n = s.size();
    s = "^" + s + "$";
    for (int i = 1; i <= n; i++)
        if (s[i] == 'Y')
            allY[++allY[0]] = i;
    for (int i = 1; i <= allY[0]; i++)
        sum[i] = sum[i - 1] + allY[i];
    int l = 0;
    int r = allY[0];
    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}