LA-4726 (斜率优化+单调队列)

题意：

给定一个01序列,选一个长度至少为L 的连续子序列使其平均值最大;输出这个子序列的起点和终点;如果有多个答案,输出长度最小的,还有多个就输出第一个编号最小的;

思路：

用sum[i]表示[1,i]的和;题目的平均值就可以变成(sum[i]-sum[j-1])/(i-(j-1));

问题也变成求横坐标的距离至少为L的两点连线斜率最大的那两点的横坐标是多少？

对于每个点作为横坐标较大的点,判断横坐标距离最少为L的点,指针r维护这些点是一个下凸线,指针l维护与当前点斜率最大点;

复杂度是O(n)的,具体的解释分析可见《浅谈数形结合在信息学竞赛中的应用》;

AC代码：

#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());

    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());

    F && (num=-num);

}

int stk[70], tp;

template<class T> inline void print(T p) {

    if(!p) { puts("0"); return; }

    while(p) stk[++ tp] = p%10, p/=10;

    while(tp) putchar(stk[tp--] + '0');

    putchar('\n');

}

const LL mod=1e9+7;

const double PI=acos(-1.0);

const int inf=1e9;

const int N=1e5+10;

const int maxn=1e3+10;

const double eps=1e-10;

char s[N];

int sum[N],a[N];

int main()

{

          int t ;

          read(t);

          while(t--)

          {

                  int n,L;

                  read(n);read(L);

                  scanf("%s",s);

                  For(i,0,n-1)

                      sum[i+1]=sum[i]+s[i]-'0';

                  //For(i,1,n)cout<<sum[i]<<" ";

                  int r = -1,l = 0,ans1=0,ans2=L,x=sum[L],y=L;

                  For(i,L,n)

                  {

                      while(r>l)

                      {

                          if((sum[i-L]-sum[a[r]])*(a[r]-a[r-1])<=(sum[a[r]]-sum[a[r-1]])*(i-L-a[r]))r--;

                          else break;

                      }

                      a[++r]=i-L;

                      while(l<r)

                      {

                          if((sum[i]-sum[a[l+1]])*(i-a[l])>=(sum[i]-sum[a[l]])*(i-a[l+1]))l++;

                          else break;

                      }

                      if((sum[i]-sum[a[l]])*y>x*(i-a[l]))

                      {

                          x=sum[i]-sum[a[l]];

                          y=i-a[l];

                          ans1=a[l];

                          ans2=i;

                      }

                      else if((sum[i]-sum[a[l]])*y==x*(i-a[l]))

                      {

                          if(i-a[l]<y)

                          {

                              x=sum[i]-sum[a[l]];

                              y=i-a[l];

                              ans1=a[l];

                              ans2=i;

                          }

                      }

                      //cout<<i<<" "<<l<<" "<<r<<"@@"<<endl;

                  }

                  cout<<ans1+1<<" "<<ans2<<"\n";

          }

        return 0;

}

巴特西

LA-4726 (斜率优化+单调队列)

最新文章

热门文章