HDU 4923 Room and Moor （多校第六场C题）单调栈

Problem Description

PM Room defines a sequence A = {A₁, A₂,..., A_N}, each of which is either 0 or 1. In order
to beat him, programmer Moor has to construct another sequence B = {B₁, B₂,... , B_N} of the same length, which satisfies
that:

HDU 4923 Room and Moor （多校第六场C题）单调栈

Input

The input consists of multiple test cases. The number of test cases T(T<=100) occurs in the first line of input.

For each test case:

The first line contains a single integer N (1<=N<=100000), which denotes the length of A and B.

The second line consists of N integers, where the ith denotes A_i.

Output

Output the minimal f (A, B) when B is optimal and round it to 6 decimals.

Sample Input

4

9

1 1 1 1 1 0 0 1 1

9

1 1 0 0 1 1 1 1 1

4

0 0 1 1

4

0 1 1 1

Sample Output

能够分析出所求的区间也就是从第一个为1開始的到最后一个0结束。每段都是形如111...111000...000这样先为1后为0 的小区间里 B值都是水平的。那么先求出当前一零区间的最优值，假设当前的高度最优值大于单调增栈里栈首元素的高度，那么能够直接入栈，假设小于，就取出栈首元素与当前区间进行合并，再次入栈。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <stack>

#define lson o<<1, l, m

#define rson o<<1|1, m+1, r

using namespace std;

typedef long long LL;

const int maxn = 100005;

const int mod = 1000000007;

int t, n, a[maxn];

struct C {

    int num1, num0;

    double res, h;

};

double Cu(double x, double y)  {

    return x*y/(x+y);

}

double Ch(double x, double y) {

    return x/(x+y);

}

int main()

{

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        int st = 1, en = n, i, j, k;

        for(i = 1; i <= n; i++) scanf("%d", &a[i]);

        for(i = 1; i <= n && a[i] == 0; i++) ; st = i;

        for(i = n; i >= 1 && a[i] == 1; i--) ; en = i;

        stack <C> zhan;

        for(i = st; i <= en; ) {

            int u = 0, d = 0;

            for(j = i; j <= en; j++) {

                if(a[j] == 0) break;

                u++;

            }

            for(k = j; k <= en; k++) {

                if(a[k] == 1) break;

                d++;

            }

            C aa;

            aa.num0 = d;

            aa.num1 = u;

            aa.res = Cu(u, d);

            aa.h = Ch(u, d);

            while(!zhan.empty() && zhan.top().h > aa.h) {

                C tmp = zhan.top();

                zhan.pop();

                aa.num1 = tmp.num1 + aa.num1;

                aa.num0 = tmp.num0 + aa.num0;

                aa.res = Cu(aa.num1, aa.num0);

                aa.h = Ch(aa.num1, aa.num0);

            }

            zhan.push(aa);

            i = k;

        }

        double sum = 0;

        while(!zhan.empty()) {

            C tmp = zhan.top();

            zhan.pop();

            sum += tmp.res;

        }

        printf("%.6lf\n", sum);

    }

    return 0;

}

HDU 4923 Room and Moor （多校第六场C题） 单调栈

HDU 4923 Room and Moor （多校第六场C题）单调栈