求助:二分得出均值答案之后,为什么是这样找区间?
查看原帖
求助:二分得出均值答案之后,为什么是这样找区间?
90036
buaa_czx楼主2023/8/13 11:56
#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;
}

按照题解的二分思路写的,二分找出平均值之后直接贪心的找左右区间,同样的只关注左边的最小值。但是为什么在寻找区间的时候只关注最小值是对的呢?不会出现一些反例情况吗

2023/8/13 11:56
加载中...