先考虑比例 $s \leq p$ 的情况。

那么我们需要使 $p - s$ 最小。

维护一个前缀和。

那么：

$$
p - s = p - \frac{sm(r) - sm(l)}{r - l} = \frac{p r - sm(r) + p l - sm(l)}{r - l}
$$

可以记点 $a_i=(i, p i - sm(i))$。

那么我们就是要求最小的非负斜率。

我们按照 $y$ 坐标排序。

我们可以证明最优的点一定相邻。

因为如果他们不相邻，那么找他们中间任意一个点都能取到更优的结果。

另一种情况同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define P pair<double,int>
#define fir first
#define sec second
const int maxn=5e5;
const double eps = 1e-8;
int n;
char s[maxn+5];
int sm[maxn+5];
double p;
P a[maxn+5];
P ans,tmp;
inline double Calc(P x,P y){
    return (x.fir-y.fir)/(x.sec-y.sec);
}
P min(P a, P b) {
    if (abs(a.fir-b.fir)<=eps)
        return a.sec<b.sec?a:b;
    return a.fir<b.fir?a:b;
}
inline void Solve(){
    scanf("%d%lf%s",&n,&p,s+1);
    ans.fir=DBL_MAX;
    for(int i=1;i<=n;i++) sm[i]=sm[i-1]+(s[i]=='1');
    for(int i=0;i<=n;i++) a[i]=P(p*i-sm[i],i);
    sort(a,a+n+1);
    for(int i=0;i<n;i++)
        if(a[i].sec<a[i+1].sec)
            ans=min(ans,{Calc(a[i],a[i+1]),a[i].sec+1});
    for(int i=0;i<=n;i++) a[i]=P(sm[i]-p*i,i);
    sort(a,a+n+1);
    for(int i=0;i<n;i++)
        if(a[i].sec<a[i+1].sec)
            ans=min(ans,{Calc(a[i],a[i+1]),a[i].sec+1});
    printf("%d\n",ans.sec);
}
signed main(){
    freopen("tii.in","r",stdin);
    freopen("tii.out","w",stdout);
    int tcnt;scanf("%d",&tcnt);
    while(tcnt--) Solve();
    return 0;
}