UVA1451

标签：md int double chk 1e include UVA1451

 

二分平均值x，每个数减去x ,    找区间 S[ r ]- S[l]>=0 ,r-l>=m

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
 const int N=1e5+5;
 #define inf 1e9
 int n,m,a[N]; double s[N];
 
 int chk(double md,int ok=0){
 	int i,k;
 	s[0]=0;for(i=1;i<=n;i++) s[i]=s[i-1]+a[i]-md;
 	double t=inf,ans=-inf;
 	double L=0,R=0 ;
 	
  	for(i=m;i<=n;i++){
  		if(s[i-m]<=t){
  			t=s[i-m]; k=i-m+1;
  		}
 		if(s[i]-t>ans+1e-6){
 			L=k,R=i;
 			ans=s[i]-t;
 		}
	}
	if(ok){
		cout<<L<<' '<<R<<endl;
	}
	return ans>=0;
 }
 signed main(){
 	int cas; cin>>cas;
 	while(cas--){
	 	cin>>n>>m;
	 	int i; char c;
	 	for(i=1;i<=n;i++) cin>>c,a[i]=c-'0';
	 	double l=0,r=1,t;
	 	
	 	while(r-l>1e-6){
	 		double md=(l+r)/2;
	 		if(chk(md)) l=md; else r=md;
		 }
		 chk(l+1e-6,1);
	}
 }
 
 
 

 

标签：md,int,double,chk,1e,include,UVA1451
From： https://www.cnblogs.com/towboa/p/17323667.html