UVALive 4726 Average ——（斜率优化DP）

　　这是第一次写斜率优化DP= =。具体的做法参照周源论文《浅谈数形结合思想在信息学竞赛中的应用》。这里仅提供一下AC的代码。

　　有两点值得注意：1.我这个队列的front和back都是闭区间的；2.在while(...) front++; 这个循环里面，<=写成<就会WA，不知道是为何（讲道理是肯定没问题的，至多多判断几个点而已，我猜想可能是存在了精度误差导致的）。。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <math.h>

 using namespace std;

 const int N = 1e5 + ;

 int n,m;

 int pre[N];

 char s[N];

 int que[N];

 double cal(int x,int y)

 {

     return 1.0 * (pre[y] - pre[x]) / (y - x);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         scanf("%s",s+);

         for(int i=;i<=n;i++) pre[i] = pre[i-] + s[i] - '';

         int front = , back = -;

         int ansl = , ansr = m;

         double ans = cal(, m);

         int len = m;

         for(int i=m;i<=n;i++)

         {

             int a = i - m;

             while(front < back && cal(que[back], a) <= cal(que[back-], a)) back--;

             que[++back] = a;

             while(front < back && cal(que[front], i) <= cal(que[front+], i)) front++;

             double temp = cal(que[front], i);

             if(temp > ans)

             {

                 ans = temp;

                 ansl = que[front];

                 ansr = i;

                 len = i - que[front];

             }

             else if(fabs(temp-ans) < 1e- && len > i - que[front])

             {

                 len = i - que[front];

                 ansl = que[front];

                 ansr = i;

             }

         }

         printf("%d %d\n",ansl + , ansr);

     }

     return ;

 }