UVa 1451 平均值

 1 #include<iostream>  
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 100000 + 5;
 6 
 7 char str[maxn];
 8 int n, L;
 9 int sum[maxn];
10 int q[maxn];
11 int front, rear;
12 
13 double cacl(int a, int b)   //计算斜率
14 {
15     return (double)(sum[b]-sum[a]) / (b-a);
16 }
17 
18 int main()
19 {
20     //freopen("D:\\txt.txt", "r", stdin);
21     int t;
22     cin >> t;
23     while (t--)
24     {
25         cin >> n >> L >> str;
26         sum[0] = 0;
27         for (int i = 1; i <= n; i++)
28             sum[i] = sum[i - 1] + str[i - 1] - ‘0‘;
29         front = rear = -1;
30         int start = 0, end = L,len=0;
31         double ans = 0;
32         //因为长度至少为L，所以从L开始
33         for (int t = L; t <= n; t++)    //t为线段右端点
34         {
35             int j = t - L;   //j为线段左端点
36             //如果rear-1，rear和j是上凸点，那么删去上凸点rear
37             while (front < rear && cacl(q[rear],j) <= cacl(q[rear - 1], q[rear]))  rear--;
38             //加入j
39             q[++rear] =j;
40             //第一个和t的斜率小于等于第二个和t的斜率，那么肯定取第二个，删去第一个
41             while (front < rear && cacl(q[front], t) <= cacl(q[front + 1], t))    front++;
42             //由上一步可得出t和q[front]斜率，这也就是t所能组成的最大斜率
43             double m = cacl(q[front], t);
44             int l = t - q[front] + 1;
45             if (m == ans && l<len || m>ans)
46             {
47                 ans = m;
48                 len = l;
49                 start = q[front];
50                 end = t;
51             }
52         }
53         cout << start + 1 << " " << end << endl;
54     }
55     return 0; 
56 }