宁波新亚建设内部网站,互联网发展趋势,北京性价比网站建设,技术网题意#xff1a;给定一个长度为n 的01串#xff0c;然后选一个长度至少为L的子串#xff0c;使得子串的平均值最大。 思路#xff1a;单调队列。如果把所有的前缀和都求出来#xff0c;那么所求即为max((s[j] - s[i]) / (j - i)) #xff0c;转化成图也就是求斜率最大的那…题意给定一个长度为n 的01串然后选一个长度至少为L的子串使得子串的平均值最大。 思路单调队列。如果把所有的前缀和都求出来那么所求即为max((s[j] - s[i]) / (j - i)) 转化成图也就是求斜率最大的那个点s[i]是不递减的那么最优解是下凸的。单调队列维护最优解当是上凸的就弹出。 code #include cstdio
using namespace std;
const int N100005;
int sm[N],q[N];
char s[N];int sol(int x1,int x2,int x3,int x4)
{return (sm[x2]-sm[x1])*(x4-x3)-(sm[x4]-sm[x3])*(x2-x1);
}
int main()
{int n,l,T;scanf(%d,T);while (T--){scanf(%d %d %s,n,l,s1);sm[0]0;for (int i1;in;i) sm[i]sm[i-1]s[i]-0;int tl0,trl;int i0,j0;for (int tl;tn;t){while(ij-1sol(q[j-1],t-l,q[j-2],t-l)0) j--;q[j]t-l;while(ij-1sol(q[i1],t,q[i],t)0) i;int ttsol(q[i],t,tl,tr);if (tt0||tt0(t-q[i]tr-tl)) trt,tlq[i];}printf(%d %d\n,tl1,tr);}
}
