683
uva 1451 - Average 數形結合
數形結合那篇論文的例題，維護一個下凸隊列，一開始為了省事，用了棧，但是原理上有問題，因為有可能正好起點為上凸點的情況，WA了好多次……
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int org[100005],l,r;
struct node
{
int v,ind;
node(int a,int b)
{
v=a;
ind=b;
}
node(){}
};
node q[100005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,L;
scanf("%d%d",&n,&L);
while(getchar()!='\n');
int i;
int now=0;
int aa=0,ab=0;
for(i=1;i<=n;i++)
{
if(getchar()=='1')now++;
org[i]=now;
}
r=0;
q[r++]=node(0,-1);
q[r++]=node(0,0);
l=1;
int ta=-1,tb=0;
for(int k=L;k<=n;k++)
{
i=k-L;
while(l<r-1&&(((org[i]-q[r-2].v)*(i-q[r-1].ind))-(org[i]-q[r-1].v)*(i-q[r-2].ind))>=0)
r--;
q[r++]=node(org[i],i);
while(l<r-1&&(((org[k]-q[l+1].v)*(k-q[l].ind))-(org[k]-q[l].v)*(k-q[l+1].ind))>=0)
l++;
if(((org[k]-q[l].v)*tb-ta*(k-q[l].ind))>0||(((org[k]-q[l].v)*tb-ta*(k-q[l].ind))==0&&(k-q[l].ind)<(ab-aa+1)))
{
aa=q[l].ind+1;
ab=k;
ta=(org[k]-q[l].v);
tb=(k-q[l].ind);
}
}
printf("%d %d\n",aa,ab);
}
}
最後更新：2017-04-03 14:53:38