Average UVALive - 4726
http://www.docin.com/p-881778722.html
这个论文说的很清楚
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<queue> #include<map> #include<set> #include<list> #include<ctime> #include<ctype.h> #include<bitset> #include<algorithm> #include<numeric> //accumulate #define endl " " #define fi first #define se second #define FOR(i,s,t) for(int i=(s);i<=(t);++i) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=100000+5; int n,k; string s; int pre[maxn]; int q[maxn]; inline double cal(int i,int j) { return 1.0*(pre[j]-pre[i])/(j-i); } int main() { //cout<<mid(25,5)<<endl; //cin.tie(0); //cout.tie(0); //ios_base::sync_with_stdio(false); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; cin>>T; while(T--) { cin>>n>>k; cin>>s; //cout<<s<<endl; for(int i=1;i<=n;i++) { pre[i]=pre[i-1]+(s[i-1]=='1'); //cout<<pre[i]<<endl; } int l=1,r=1; q[l]=0; int ans_l=0,ans_r=k; for(int i=k+1;i<=n;i++) { int t=i-k; while(l<r&&cal(q[r],t)<=cal(q[r-1],q[r])) r--; q[++r]=t; while(l<r&&cal(q[l],i)<=cal(q[l+1],i)) { l++; } if(cal(ans_l,ans_r)<cal(q[l],i)) { ans_l=q[l]; ans_r=i; } else if(cal(ans_l,ans_r)==cal(q[l],i)) { if(i-q[l]<ans_r-ans_l) { ans_l=q[l]; ans_r=i; } } } cout<<ans_l+1<<' '<<ans_r<<endl; } } /* void read() { char c = getchar(); int x = 0; for (; (c < 48 || c>57); c = getchar()); for (; c > 47 && c < 58; c = getchar()) { x = (x << 1) + (x << 3) + c - 48; } return x; } */