题意：求连续的子序列使得平均数最大
思路：一切尽在
《浅谈数形结合思想在信息学竞赛中的应用》
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
char str[MAXN];
int q[MAXN],sum[MAXN];
int n,m;
double dis(int a,int b){
return (sum[b]-sum[a])*1.0/(b-a);
}
int main(){
int t;
scanf("%d",&t);
while (t--){
scanf("%d%d",&n,&m);
scanf("%s",str+1);
sum[0] = 0;
for (int i = 1; i <= n; i++)
sum[i] = sum[i-1] + str[i] - ‘0‘;
int ansl = 0,ansr = m;
double ans = dis(0,m);
int front = 0,rear = -1,len = m;
for (int i = m; i <= n; i++){
int ita = i - m;
while (front < rear && dis(q[rear],ita) <= dis(q[rear-1],ita))
rear--;
q[++rear] = ita;
while (front < rear && dis(q[front],i) <= dis(q[front+1],i))
front++;
double itb = dis(q[front],i);
if (itb > ans){
ans = itb;
ansl = q[front];
ansr = i;
len = i - q[front];
}
else if (itb == ans && len > i - q[front]){
ansl = q[front];
ansr = i;
len = i - q[front];
}
}
printf("%d %d\n",ansl+1,ansr); //注意sum[]的定义，所以+1
}
return 0;
}