P1404 平均数

题目描述

给一个长度为 nn 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 \ge m≥m。

输入格式

第一行两个整数 nn 和 mm。

接下来 nn 行，每行一个整数 a_iai​，表示序列第 ii 个数字。

输出格式

一个整数，表示最大平均数的 10001000 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

输入输出样例

输入 #1复制

10 6
6
4
2
10
3
8
5
9
4
1

输出 #1复制

6500

说明/提示

数据规模与约定

• 对于 60\%60% 的数据，保证 m\le n\le 10^4m≤n≤104；
• 对于 100\%100% 的数据，保证 1 \leq m\le n\le 10^51≤m≤n≤105，0\le a_i\le20000≤ai​≤2000。

二分答案自然是平均数一类问题的常用思路。不过这题还有O(n)的算法（参见2004年集训队论文，周源）

大体思路是先求部分和S(x)，然后连续子序列平均值就转化为S-x平面上的斜率：ave(x,y)=(S(y)-s(x-1))/(y-x+1)。考虑x<y<z的三个点如果S(y)是上凸的，则这个点一定没贡献。所以有用的点构成一个下凸的折线

用一个队列维护这个折线，加入新点时（如当前点为i，则新点为i-m），如果与队尾2个点形成上凸，则删除队尾点。如果队首2个点与当前点形成上凸，同理删除队首点。最后每次队首元素都是与点i斜率最大的点，再求最值就行了

这个方法还可以求以每个点结尾的满足条件的最大平均数，这样子二分答案就不行啦，hoho~~

二分答案 每次判断能不能满足存在长度大于m的子串的平均值>=mid就好 复杂度为O（n log 2000000）

至于怎么判断可以把数列每一项减去mid 如果存在前缀和s[i]< s[j] && j-i>=m那么就满足条件

#include <iostream>
#include <cmath>
#define N 100005
typedef long long ll;
using namespace std;

ll n,m,s[N];
double ans=0.0;
ll q[N],t,h;   // 队列

double k(ll x,ll y){  // 计算s[x],s[y]的斜率
    return (s[y]-s[x]+0.0)/(y-x);
}

int main() {
    cin>>n>>m;
    for (ll i=1,x;i<=n;i++){
        cin>>x; s[i]=s[i-1]+x;
    }

    for (ll i=m;i<=n;i++){
        while (t-h>=2 && k(i-m,q[t-1])<k(i-m,q[t-2])) t--;   // 删除上凸点
        q[t++]=i-m;  // 入队
        while (t-h>=2 && k(i,q[h])<k(i,q[h+1])) h++;  // 移动最大斜率点
        ans=max(ans,k(i,q[h]));
    }
    
    cout<<(ll)floor(ans*1000)<<endl;
    return 0;
}