比赛 20241126 评测结果 AAAAAAAAAA
题目名称 小b爱实数 最终得分 100
用户昵称 darkMoon 运行时间 1.911 s
代码语言 C++ 内存使用 47.74 MiB
提交时间 2024-11-26 10:50:33
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("changgao_real.in", "r", stdin);
auto OUT = freopen("changgao_real.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 1e6 + 5;
double f;
char s[N];
double b[N], tmp[N];
int sum[N], n;
signed main(){
    cin >> f;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i ++){
        sum[i] = sum[i - 1];
        if(s[i] == '1'){
            sum[i] ++;
        }
        b[i] = (double)sum[i] / f;
        tmp[i] = b[i] - i;
    }
    double mii = 1;
    int ans = 0;
    multiset<pair<double, int>> se;
    se.insert(mp(0, 0));
    for(int i = 1; i <= n; i ++){
        auto it = se.lower_bound(mp(tmp[i], -1));
        int p;
        if(it != se.end()){
            p = (*it).se;
            if(fabs((1.0 * (sum[i] - sum[p])) / (1.0 * (i - p)) - f) < mii){
                mii = fabs((1.0 * (sum[i] - sum[p])) / (1.0 * (i - p)) - f);
                ans = p;
            }
        }

        it = se.upper_bound(mp(tmp[i], 0x3f3f3f3f));
        if(it != se.begin()){
            it --;
            p = (*it).se;
            if(fabs((1.0 * (sum[i] - sum[p])) / (1.0 * (i - p)) - f) < mii){
                mii = fabs((1.0 * (sum[i] - sum[p])) / (1.0 * (i - p)) - f);
                ans = p;
            }
        }
        se.insert(mp(tmp[i], i));
    }
    printf("%lld", ans);
    return 0;
}