比赛 |
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;
}