#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
int n, L;
char s[maxN + 5];
double a[maxN + 5], b[maxN + 5];
bool check(double x) {
b[0] = 0.0;
rep(i, 1, n) b[i] = (double)a[i] - x;
rep(i, 1, n) b[i] += b[i - 1];
double minn = 1e8;
rep(i, L, n) {
minn = min(minn, b[i - L]);
if (b[i] + eps > minn)
return 1;
}
return 0;
}
void solve() {
scdd(n, L);
scs(s + 1);
rep(i, 1, n) { a[i] = s[i] - '0'; }
double l = 0.0, r = 1.0;
while (l + eps < r) {
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
double x = l, minn = 1e8;
int ansl, ansr, curl, fl = 0;
// pr("%.10lf\n", l);
b[0] = 0.0;
rep(i, 1, n) b[i] = (double)a[i] - x;
rep(i, 1, n) b[i] += b[i - 1];
rep(i, L, n) {
if (b[i - L] < minn + eps) {
curl = i - L + 1;
minn = b[i - L];
}
if (b[i] + eps > minn) {
if (!fl) {
ansl = curl, ansr = i;
} else if (i - curl < ansr - ansl) {
ansl = curl, ansr = i;
}
fl = 1;
}
}
pr("%d %d\n", ansl, ansr);
}
int main() {
cf;
return 0;
}
按照题解的二分思路写的,二分找出平均值之后直接贪心的找左右区间,同样的只关注左边的最小值。但是为什么在寻找区间的时候只关注最小值是对的呢?不会出现一些反例情况吗