Dirt Ratio

Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1473 Accepted Submission(s): 683
Special Judge

Problem Description

In ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed Xproblems during the contest, and submitted Y times for these problems, then the ''Dirt Ratio'' is measured as XY. If the ''Dirt Ratio'' of a team is too low, the team tends to cause more penalty, which is not a good performance.

Picture from MyICPCLittle Q is a coach, he is now staring at the submission list of a team. You can assume all the problems occurred in the list was solved by the team during the contest. Little Q calculated the team's low ''Dirt Ratio'', felt very angry. He wants to have a talk with them. To make the problem more serious, he wants to choose a continuous subsequence of the list, and then calculate the ''Dirt Ratio'' just based on that subsequence.
Please write a program to find such subsequence having the lowest ''Dirt Ratio''.

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there is an integer n(1≤n≤60000) in the first line, denoting the length of the submission list.
In the next line, there are n positive integers a1,a2,...,an(1≤ai≤n), denoting the problem ID of each submission.

Output

For each test case, print a single line containing a floating number, denoting the lowest ''Dirt Ratio''. The answer must be printed with an absolute error not greater than 10−4.

Sample Input

1
5
1 2 1 2 3

Sample Output

0.5000000000

Hint

For every problem, you can assume its final submission is accepted.

【题意】给你一个序列，问你对于任意子序列，序列中数的种数/区间长度最小是多少。

【分析】二分答案midmid，检验是否存在一个区间满足cnt(l,r)/(r-l+1)≤mid，

也就是cnt(l,r)+mid*l<=mid*(r+1)。从左往右枚举每个位置作为r，

当r变化为r+1时，对cnt的影响是一段区间加1，线段树维护区间最小值即可。线段树维护的是当枚举到r时，每个区间内cnt(l,r)+mid*l的最小值，

跟mid*(r+1)比较大小即可。这个题跟Codeforces Round #426 (Div. 2) D The Bakery很像，代码几乎一样，思想相同。

http://www.cnblogs.com/jianrenfang/p/7265602.html

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define mp make_pair

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 6e4+;;

const int M = ;

const int mod = 1e9+;

const double pi= acos(-1.0);

typedef pair<int,int>pii;

int n,k,ans;

int a[N],lazy[N*];

int pre[N],pos[N];

double dp[N];

double mx[N*];

void pushUp(int rt){

    mx[rt]=min(mx[rt<<],mx[rt<<|]);

}

void pushDown(int rt){

    if(lazy[rt]){

        lazy[rt<<]+=lazy[rt];

        lazy[rt<<|]+=lazy[rt];

        mx[rt<<]+=lazy[rt];

        mx[rt<<|]+=lazy[rt];

        lazy[rt]=;

    }

}

void build(int l,int r,int rt,double x){

    lazy[rt]=;

    if(l==r){

        mx[rt]=x*l;

        return;

    }

    int mid=(l+r)>>;

    build(l,mid,rt<<,x);

    build(mid+,r,rt<<|,x);

    pushUp(rt);

}

void upd(int L,int R,int l,int r,int x,int rt){

    if(L<=l&&r<=R){

        mx[rt]+=x;

        lazy[rt]+=x;

        return;

    }

    pushDown(rt);

    int mid=(l+r)>>;

    if(L<=mid)upd(L,R,l,mid,x,rt<<);

    if(R>mid) upd(L,R,mid+,r,x,rt<<|);

    pushUp(rt);

}

double qry(int L,int R,int l,int r,int rt){

    if(L<=l&&r<=R){

        return mx[rt];

    }

    pushDown(rt);

    double ret=;

    int mid=(l+r)>>;

    if(L<=mid)ret=min(ret,qry(L,R,l,mid,rt<<));

    if(R>mid)ret=min(ret,qry(L,R,mid+,r,rt<<|));

    return ret;

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        met(pos,);

        scanf("%d",&n);

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

            pre[i]=pos[a[i]];

            pos[a[i]]=i;

        }

        double l=,r=;

        for(int i=;i<=;i++){

            double mid = (l+r)/;

            build(,n,,mid);

            bool ok=true;

            for(int j=;j<=n;j++){

                upd(pre[j]+,j,,n,,);

                dp[j]=qry(,j,,n,);

                if(dp[j]<=mid*(j+)){

                    ok=false;break;

                }

            }

            if(!ok)r=mid;

            else l=mid;

        }

        printf("%.9f\n",(l+r)/);

    }

}

巴特西

HDU 6070 Dirt Ratio（线段树）

Dirt Ratio

最新文章

热门文章