HDU6070（分数规划+线段树）

深碍√TFBOYSˉ_ 2022-06-11 09:38 189阅读 0赞

## 题目链接：[HDU6070][] ##

--------------------

## 题目大意： ##

给你长度为n的序列，求某个区间[l,r]使得区间内的数字种类/区间长度最小
    输出这个最小值

--------------------

## 题目思路： ##

对于这种区间最优比率问题（分数规划问题）我们常规的解法是二分答案来求
    根据题目意思我们二分答案后可以转化成
    size(l,r)/(r-l+1)<=mid   ->   size(l,r)+l*mid <=(r+1)*mid
    这里我们可以枚举右边的r ，然后用最值线段树来维护左边的最小值，  
    我们build的时候将线段树初始化为l*mid,然后对于枚举i,a[i]的贡献区间为
    [pre[a[i]]+1,i]+1 因为如果前面已经存在了a[i]，该数就对之前的区间
    没有贡献了

--------------------

## AC代码： ##

#include<bits/stdc++.h>
    const int maxn = 6e4+50;
    const double esp = 1e-5;
    using namespace std;
    int a[maxn],last[maxn],pre[maxn],n;
    double tree[maxn<<2],c[maxn<<2];
    void pushup(int rt){tree[rt] = min(tree[rt<<1],tree[rt<<1|1]);}
    void pushdown(int rt)
    {
        if(c[rt]>0)
        {
            c[rt<<1]+=c[rt];
            c[rt<<1|1]+=c[rt];
            tree[rt<<1]+=c[rt];
            tree[rt<<1|1]+=c[rt];
            c[rt] = 0;
        }
    }
    void Build(int l,int r,int rt,double mid)
    {
        c[rt] =0;
        if(l==r)
        {
            tree[rt] = mid*l*1.0;
            return ;
        }
        int Mid = (l+r)>>1;
        Build(l,Mid,rt<<1,mid);
        Build(Mid+1,r,rt<<1|1,mid);
        pushup(rt);
    }
    
    void updata(int l,int r,int rt,int L,int R,double x)
    {
        if(L<=l&&r<=R)
        {
            tree[rt]+=x;
            c[rt]+=x;
            return ;
        }
        pushdown(rt);
        int mid = (l+r)>>1;
        if(L<=mid)
        {
            updata(l,mid,rt<<1,L,R,x);
        }
        if(R>mid)
        {
            updata(mid+1,r,rt<<1|1,L,R,x);
        }
        pushup(rt);
    }
    double quary(int l,int r,int rt,int L,int R)
    {
        if(L<=l&&r<=R)
        {
            return tree[rt];
        }
        pushdown(rt);
        int mid = (l+r)>>1;
        double res = 1e9;
        if(L<=mid)
        {
            res = min(res,quary(l,mid,rt<<1,L,R));
        }
        if(R>mid)
        {
            res = min(res,quary(mid+1,r,rt<<1|1,L,R));
        }
        return res;
    }
    bool check(double mid)
    {
        Build(1,n,1,mid);
        for(int i=1;i<=n;i++)
        {
            updata(1,n,1,pre[i]+1,i,1.0);
            if(quary(1,n,1,1,i)<=mid*(i+1.0))return true;
        }
        return false;
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--)
        {
            scanf("%d",&n);
            memset(last,0,sizeof(last));
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                if(last[a[i]])
                {
                    pre[i] = last[a[i]];
                }
                else pre[i] = 0;
                last[a[i]] = i;
            }
            double l = 0,r = 1.0,mid,ans;
            while(r-l>esp)
            {
                mid = (l+r)/2.0;
                if(check(mid))r = (ans=mid)-esp;
                else l = mid+esp;
            }
            printf("%lf\n",ans);
        }
        return 0;
    }

[HDU6070]: http://acm.hdu.edu.cn/showproblem.php?pid=6070