A simple Blog for wyx I've been down the bottle hoping.
4476: [Jsoi2015]送礼物
发表于: | 分类: Oi | 评论:0 | 阅读:179

这题不是非常的难,但是是一道非常优秀的题目

首先你需要知道一个东西叫分数规划,不知道的自己百度

先考虑答案的区间有什么性质,容易发现答案的区间要么长度是$L$,要么就是最大值最小值分别在两边这样的形势,对于第一种情况,随便什么扫扫就行了,对于第二种情况我们进行分数规划,假设答案是$ans$,那么对于任意的$i,j$都有

$\frac{M(i,j)-m(i,j)}{j-i+k} \le ans$
$M(i,j)-m(i,j)\le ans\times (j-i+k)$
$M(i,j)-m(i,j)-ans\times (j-i+k) \le 0$
$M(i,j)-m(i,j)-ans\times j + ans \times i - ans \times k \le 0$
假设答案区间是$[Max,Min]$的形势,那么刚才的柿子就能化为
$a_i-a_j-ans\times j + ans \times i - ans \times k \le 0$
$a_i + ans \times i a_j - ans \times j - ans \times k \le 0$
定义$calc(i) = a_i +ans \times i$
然后这个东西就变成了
$calc(i)-calc(j)-ans\times k \le 0$
然后用线段树维护$calc(i)$的最小值,每次直接枚举一下区间的右端点然后瞎算算就行了

我的复杂度是$O(n\log^2(n))$的,上述的所有“扫扫”都用线性数据结构的话即可做到一个$\log$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e4+5;
const int M = N << 2;

double tr[M],tmptr[M];
double a[N],b[N];

void build(int k,int l,int r) {
    if(l==r) {
        tr[k] = b[l];
        return ;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k] = min(tr[k<<1],tr[k<<1|1]);
}

inline double ask(int k,int l,int r,int x,int y) {
    if(l==x && r==y) return tr[k];
    int mid = (l+r) >> 1;
    if(y <= mid) return ask(k<<1,l,mid,x,y);
    else if(x > mid) return ask(k<<1|1,mid+1,r,x,y);
    else return min(ask(k<<1,l,mid,x,mid),ask(k<<1|1,mid+1,r,mid+1,y));
}

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

void tmpbuild(int k,int l,int r) {
    if(l==r) {
        tmptr[k] = b[l];
        return ;
    }
    int mid = (l+r) >> 1;
    tmpbuild(k<<1,l,mid);
    tmpbuild(k<<1|1,mid+1,r);
    tmptr[k] = max(tmptr[k<<1],tmptr[k<<1|1]);
}

inline double tmpask(int k,int l,int r,int x,int y) {
    if(l==x && r==y) return tmptr[k];
    int mid = (l+r) >> 1;
    if(y <= mid) return tmpask(k<<1,l,mid,x,y);
    else if(x > mid) return tmpask(k<<1|1,mid+1,r,x,y);
    else return max(tmpask(k<<1,l,mid,x,mid),tmpask(k<<1|1,mid+1,r,mid+1,y));
}

int main() { //freopen("C.in","r",stdin); freopen("C.out","w",stdout);
    int TTTT; cin >>  TTTT; while(TTTT--) {
        int n = read(), K = read(), L = read(), R = read();
        for(int i=1;i<=n;++i)  a[i] = b[i] = read();
        build(1,1,n);
        tmpbuild(1,1,n);
        double ans = 0;
        int times = 25;
        for(int i=1;i<=n-L+1;++i) {
            double tmp = tmpask(1,1,n,i,i+L-1) - ask(1,1,n,i,i+L-1);
            tmp = tmp / (L-1+K);
            ans = max(ans,tmp);
        }
        double l = ans, r = 1000;
        while(times -- ) {  
            double mid = (l+r) / 2.0;
            double tmp = mid * K;
            bool flag = false;      
            {//[Min,Max]
                for(int i=1;i<=n;++i) b[i] = a[i] - mid * i;
                build(1,1,n);
                for(int i=L;i<=n;++i) {
                    double tt = b[i] - ask(1,1,n,max(i-R+1,1),i-L+1);
                    if(tt > tmp) flag = true;
                }
            }   

            {// [Max,Min]
                for(int i=1;i<=n;++i) b[i] = a[i] + mid * i;
                build(1,1,n);
                for(int i=1;i<=n-L+1;++i) {
                    double tt = b[i] - ask(1,1,n,i+L-1,min(i+R-1,n));
                    if(tt > tmp) flag = true;
                }
            }
            if(flag) l = mid;
            else r = mid;
        }   
        printf("%.4lf\n",l);
     }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP