HDU-6070: Dirt Ratio （二分 + 线段树）

线段树

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 X problems 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 MyICPC

Little 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 $a_1,a_2,...,a_n(1≤a_i≤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.

题意：可以理解为，给出n次提交的题号，每次提交都是AC的，要你选出一段区间，满足这段区间的有效AC率最低，问这个最低有效的AC率是多少。

分析：二分答案mid，通过的题目数量是cnt个，区间长度为r-l+1，那么$\frac{cnt}{r-l+1}=mid$，移项得到式子$cnt+mid*l=mid*(r+1)$。当$cnt+mid*l≤mid*(r+1)$，二分左区间，否则二分右区间。我们枚举右端点，用线段树维护左边最小值，建树时，初始化为l*mid，对于每个a[i],贡献区间为[pre[a[i]]+1,i]，即其上一次出现位置的后一个位置到当前位置，我们把这个区间+1。找到区间最小值，那么就是以当前位置结尾的所有区间中的最小值。

• 代码：

#include <bits/stdc++.h>
#define eps 1e-4
using namespace std;
typedef long long LL;
const int maxn = 6e4 + 10;
int a[maxn], pre[maxn];
int n;
struct node
{
    int l, r;
    double lazy, minx;
} s[4 * maxn];
void build (int id, int l, int r, double x)
{
    s[id].l = l;
    s[id].r = r;
    s[id].lazy = 0;
    if (l == r)
        s[id].minx = (double) l * x;
    else
    {
        int mid = (l + r) / 2;
        build (id * 2, l, mid, x);
        build (id * 2 + 1, mid + 1, r, x);
        s[id].minx = min (s[id * 2].minx, s[id * 2 + 1].minx);
    }
}
void pushdown (int id)
{
    s[id * 2].lazy += s[id].lazy;
    s[id * 2 + 1].lazy += s[id].lazy;
    s[id * 2].minx += s[id].lazy;
    s[id * 2 + 1].minx += s[id].lazy;
    s[id].lazy = 0;
}
void update (int id, int l, int r, double val)
{
    if (l <= s[id].l && r >= s[id].r)
    {
        s[id].minx += val;
        s[id].lazy += val;
        return;
    }
    pushdown (id);
    int mid = (s[id].l + s[id].r) / 2;
    if (l <= mid)
        update (id * 2, l, r, val);
    if (r > mid)
        update (id * 2 + 1, l, r, val);
    s[id].minx = min (s[id * 2].minx, s[id * 2 + 1].minx);
}
double query (int id, int l, int r)
{
    if (l <= s[id].l && s[id].r <= r)
        return s[id].minx;
    pushdown (id);
    int mid = (s[id].l + s[id].r) / 2;
    if (r <= mid)
        return query (id * 2, l, r);
    else if (l > mid)
        return query (id * 2 + 1, l, r);
    else
        return min (query (id * 2, l, r), query (id * 2 + 1, l, r));
}
int check (double mid)
{
    memset (pre, 0, sizeof (pre) );
    build (1, 1, n, mid);
    for (int i = 1; i <= n; i++)
    {
        int l = pre[a[i]] + 1;
        int r = i;
        pre[a[i]] = i;
        update(1, l, r, 1);
        if (query(1, 1, r) <= mid * (r + 1))
            return 1;
    }
    return 0;
}
int main()
{
    int t;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf ("%d", &a[i]);
        double l = 0, r = 1;
        while (r - l > eps)
        {
            double mid = (l + r) / 2;
            if (check (mid) ) r = mid;
            else l = mid;
        }
        printf ("%.10lf\n", l);
    }
    return 0;
}