SS241109B. tii(tii)
题意
给你一个 \(01\) 序列,长度为 \(n \le 5\times 10^5\)。给你一个小数 \(p\),要你找出一个区间满足区间 \(1\) 的个数比区间长度和 \(p\) 最接近,输出区间的左端点,如果有多个区间输出左端点最小的那个。
思路
设 \(s\) 是原序列的前缀和数组,翻译一下题面就是求 \(|p-\frac{s_r-s_l}{r-l}|\) 最小,输出 \(l+1\)。
算一下式子:
\[|p-\frac{s_r-s_l}{r-l}|=|\frac{(pr-s_r)-(p_l-s_l)}{r-l}| \]这相当于两点斜率绝对值最小,\((i,pi-s_i)\)。
观察发现,\(s_i\) 每次可能增加 \(1\) 或者不变,\(pi\) 每次增加 \(p<1\),因此可以画出函数 \(pi-s_i\) 的图像。
要使两点间斜率最小,发现一定是选择 \(y\) 坐标相邻的两点。感性理解?
然后就对点排个序,再 \(O(n)\) 扫一遍更新答案即可。
时间复杂度是 \(O(n\log n)\),瓶颈在于排序。
code
代码很好写啊。
注意精度问题,因此判断相等和小于需要根据 eps 判断,尤其注意小于的细节:
bool less (ld a,ld b) { return b-a>eps; }
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace Vivid {
constexpr int N=5e5+7,base=1e6;
typedef long double ld;
constexpr ld inf=1e9,eps=1e-10;
int t,n;
ld p;
int b[N];
char a[N];
ld c[N];
int rk[N];
bool cmp (int a,int b) { return c[a]!=c[b] ? c[a]<c[b] : a<b; }
int ans;
ld mn;
ld abs(ld x) { return x>=0 ? x : -x; }
bool equal (ld a,ld b) { return abs(a-b)<=eps; }
bool less (ld a,ld b) { return b-a>eps; }
void main() {
sf("%d",&t);
while(t--) {
mn=inf;
ans=0;
sf("%d%Lf%s",&n,&p,a+1);
rk[0]=0;
rep(i,1,n) b[i]=b[i-1]+a[i]-'0', c[i]=p*i-b[i], rk[i]=i;
sort(rk,rk+n+1,cmp);
rep(i,1,n) {
ld x=abs((c[rk[i]]-c[rk[i-1]])/(rk[i]-rk[i-1]));
if(less(x,mn)) ans=min(rk[i-1],rk[i]), mn=x;
else if(equal(x,mn)) ans=min(ans,min(rk[i-1],rk[i]));
}
pf("%d\n",ans+1);
}
}
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("tii.in","r",stdin);
freopen("tii.out","w",stdout);
#endif
Vivid :: main();
}
标签:ld,int,SS241109B,mn,tii,ans,rk
From: https://www.cnblogs.com/liyixin0514/p/18536814