Uval4726-数形结合的思想

题意：给定一段01序列，求一段长度不小于L的连续序列，使其平均值最大

思路：一看就想到了斜率优化，但是用基本的推公示一直没推出来，看了别人的代码，像推出斜率的式子一直没弄出来。。后来一看别人写的题解，原来是数形结合可以推出斜率单调。然后维护一个下凹的队列（斜率要递增）。至于为什么这么做，可以吧sum[i]（把开头到当前的和）看作纵坐标，i当作横坐标，然后做出图，就会发现实际上就是找横坐标之差大于等于L的点形成直线斜率最大。那么在纸上画一下，结论就很明显了。。

当然，出了这种方法外，还有二分最大斜率，然后在判定的方法。。(判定时把每个数减去，斜率，接着用类似最大子序列合的方法，这种方法具体我没写过，不过有人好像就是这样过的)

不过想想，其实两种本质上应该是一种，只不过求斜率的方法一个O(1),一个log(N)而已

---------不懂看一下周源大神的论文《浅谈数形结合思想在信息学竞赛中的应用》讲的很明白

ps.poj2018也是同样的题，有空再去写一下了。

**********************************************************************

 1 /*
 2  * Author:  yzcstc
 3  * Created Time:  2013/8/18 0:35:49
 4  * File Name: uval4726.cpp
 5  */
 6 #include<iostream>
 7 #include<sstream>
 8 #include<fstream>
 9 #include<vector>
10 #include<list>
11 #include<deque>
12 #include<queue>
13 #include<stack>
14 #include<map>
15 #include<set>
16 #include<bitset>
17 #include<algorithm>
18 #include<cstdio>
19 #include<cstdlib>
20 #include<cstring>
21 #include<cctype>
22 #include<cmath>
23 #include<ctime>
24 #include<utility>
25 #define M0(x) memset(x, 0, sizeof(x))
26 #define Inf 0x7fffffff
27 #define PB push_back
28 #define SZ(v) ((int)(v).size())
29 #define eps 1e-8
30 using namespace std;
31 int n , L, TT;
32 int Y[100010], q[100100];
33 
34 double ratio(int i, int j){
35    return i == j ? Inf : (Y[j] - Y[i] + 0.0)/(j - i + 0.0);
36 }
37 
38 void solve(){
39     scanf("%d%d", &n, &L);
40     Y[0] = 0;
41     for (int i = 1; i <= n; ++i){
42         scanf("%1d", &Y[i]);
43         Y[i] += Y[i-1];
44     }
45     M0(q);
46     int l = 1, r = 0, ansl = 0, ansr = n;
47     double ans = -1;
48     for (int i = L; i <= n; ++i){
49         while (l < r && ratio(q[r - 1], q[r]) >= ratio(q[r - 1], i - L)) --r;
50         q[++r] = i - L;
51         while (l < r && ratio(q[l], i) <= ratio(q[l + 1], i)) ++l;
52         if (ans + eps < ratio(q[l], i) || fabs(ans - ratio(q[l], i)) < eps && i - q[l] < ansr - ansl){
53               ans = ratio(q[l], i);
54               ansl = q[l];
55               ansr = i;
56         }
57     }
58     printf("%d %d
", ansl + 1, ansr);
59 }
60 
61 int main(){
62    // freopen("a.in","r",stdin);
63   //  freopen("a.out","w",stdout);
64     scanf("%d", &TT);
65     while (TT--){
66           solve();
67     }
68   //  fclose(stdin); fclose(stdout);
69     return 0;
70 }