网站除了做流量还需要什么,怎么修改网站网页的背景图片,深圳门窗在哪里网站做推广,网络推广公司外包解析
这道题寻找平均值的max#xff0c;答案明显具有单调性#xff0c;所以采用二分算法 从0到1不断取中点mid作为平均值的可能点#xff0c;看是否存在不短于l的数列均值#xff1e;mid不难得到以下代码#xff1a;
double st0,ed1;for(int i1;i10;i){double mid(s…
解析
这道题寻找平均值的max答案明显具有单调性所以采用二分算法 从0到1不断取中点mid作为平均值的可能点看是否存在不短于l的数列均值mid不难得到以下代码
double st0,ed1;for(int i1;i10;i){double mid(sted)/2;if(check(mid)) stmid;else edmid;}现在的问题就是要解决这个check函数的写法了 因为N范围到1e5暴力的On方肯定是会超的 我们想到可以先把数组都减mid这样就转化为是否存在不短于L的数列加和大于等于0的问题 我们用s[i]表示1到i的加和 那么a到b的和可以转化为s[b] - s[a-1]其中b-a1 l 要使s[b] - s[a-1]最大就要使s[a-1]取的是s[0]到s[b-l1]的最大值 而随着b从l循环到n每次s[a-1]只加入了一个可能取的元素故只需与该新值取min不必遍历 代码如下
double mnM;for(int il;in;i){mnmin(mn,s[i-l]);if(s[i]-mn0) return true;//只要存在就返回true }return false;这样check函数的时间复杂度就为On
AC快乐~~~~~~
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
using namespace std;
const int M 2e9;
int n,l,t;
int zuo,you;
int f[100500];
bool check(double x){double s[100500]{ };s[1]f[1] - x;for(int i2;in;i){s[i] s[i-1] f[i] -x;//求减完x的前缀和 }double mnM;for(int il;in;i){mnmin(mn,s[i-l]);if(s[i]-mn0) return true;//只要存在就返回true }return false;
}
int main(){scanf(%d,t);for(int k1;kt;k){scanf(%d%d,n,l);for(int i1;in;i){scanf(%1d,f[i]);}double st0,ed1;for(int i1;i10;i){double mid(sted)/2;if(check(mid)) stmid;else edmid;}double xst;double s[100500]{ };s[1]f[1] - x;for(int i2;in;i){s[i] s[i-1] f[i] -x;}int a,flag0;double mnM;for(int il;in;i){if(mns[i-l]){mns[i-l];ai-l;}if(s[i]-mn0){if(flag0){zuoa1;youi;flag1;}else if(you-zuoi-a){zuoa1;youi;}}}printf(%d %d\n,zuo,you);}return 0;
}祝大家rp
