[HOJ] 302 最大平均值

二分搜平均值
驗證用貪心弄成單調序列
再從deque前面檢查

之前用凸包法不知道為什麼第12筆測資過不去

#include<cstdio>
#include<algorithm>
#include<queue>
#define MAX 100005
#define LL long long
using namespace std;
long long sum[MAX],a[MAX],tmp,l,r,mid;
int n,f;
struct node{
    int pos;
    LL val;
};
deque<node> dq;
bool ok(LL k){
    for(int i=1;i<=n;i++){
        tmp=sum[i]-k*i;
        while(!dq.empty()&&dq.back().val<=tmp)
            dq.pop_back();
        dq.push_back(node{i,tmp});
    }
    for(int i=0;i<=n;i++){
        tmp=sum[i]-k*i;
        while(!dq.empty()&&dq.front().pos<i+f)
            dq.pop_front();
        if(!dq.empty()&&dq.front().val>=tmp)return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tmp);
        sum[i]=sum[i-1]+tmp*1000;
        r=max(tmp*1000,r);
    }
    r++;
    while(l!=r-1){
        mid=l+r>>1;
        while(!dq.empty())dq.pop_front();
        if(ok(mid))l=mid;
        else r=mid;
    }
    printf("%lld\n",l);
}