8925번: GC-비율

https://www.acmicpc.net/problem/8925

#include<cstdio>
#include<deque>
using namespace std;
int t, n, m, s[100001], l, r;
double ave;
bool f(double x) {
    double mini = 0;
    for (int i = m; i <= n; i++) {
        if (mini > s[i - m] - (i - m)*x) mini = s[i - m] - (i - m)*x;
        if (s[i] - i*x >= mini) return 1;
    }
    return 0;
}
bool g(int x) {
    deque<pair<double, int> > dq;
    for (int i = m; i <= n; i++) {
        if (!dq.empty() && dq.front().second < i - x) dq.pop_front();
        while (!dq.empty() && dq.back().first > s[i - m] - (i - m)*ave) dq.pop_back();
        dq.push_back({ s[i - m] - (i - m)*ave,i - m });
        if (dq.front().first < s[i] - i*ave + 1e-9) {
            l = dq.front().second + 1;
            r = i;
            return 1;
        }
    }
    return 0;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%1d", s + i), s[i] += s[i - 1];
        double s1 = 0, e1 = 1, m1;
        while (e1 - s1>1e-15) {
            m1 = (s1 + e1) / 2;
            f(m1) ? s1 = m1 : e1 = m1;
        }
        ave = m1;
        int s2 = m, e2 = n, m2;
        while (s2 <= e2) {
            m2 = (s2 + e2) / 2;
            g(m2) ? e2 = m2 - 1 : s2 = m2 + 1;
        }
        printf("%d %d\n", l, r);
    }
    return 0;
}