HDU 4924 Room and Moor

题目链接

题意：给定一个01组成的a序列。要求一个b序列，b序列每一个数值为[0, 1]之间的数，而且b序列为非递减序列，要求∑(ai−bi)2最小，求这个最小值

思路：推理，非常easy看出，开头一段的0和末尾一段的1等于没有。然后中间每段相似111000这样1在前，0在后的序列。都能够列出一个公式，非常easy推出选择的x为共同的一个值，为1的个数/（1的个数+0的个数）a,那么问题就变成要维护一个递增的x。利用一个栈去做维护，假设遇到一个位置递减了。那么就把它和之前的段进行合并，维护栈中递增，最后把栈中元素都拿出来算一遍就是答案了

代码：

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

const int N = 100005;

const double eps = 1e-8;

int t, n, a[N];

struct Seg {

    double one, zero, x;

    Seg() {}

    Seg(double one, double zero, double x) {

    this->one = one;

    this->zero = zero;

    this->x = x;

    }

} s[N];

double cal(double one, double zero) {

    return one / (one + zero);

}

double solve(int n) {

    int sn = 0;

    int one = 0, zero = 0, now = 0;

    while (now < n && !a[now]) {now++;}

    while (n >= 0 && a[n]) n--;

    if (now > n) return 0.0;

    while (now <= n) {

    double one = 0, zero = 0;

    while (a[now]) {

        one += 1;

        now += 1;

    }

    while (now <= n && !a[now]) {

        zero += 1;

        now += 1;

    }

    s[sn].one = one;

    s[sn].zero = zero;

    s[sn++].x = cal(one, zero);

    }

    stack<Seg> st;

    st.push(s[0]);

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

    Seg now = s[i];

    while (!st.empty() && st.top().x - now.x > -eps) {

        Seg pre = st.top();

        st.pop();

        pre.one += now.one;

        pre.zero += now.zero;

        pre.x = cal(pre.one, pre.zero);

        now = pre;

    }

    st.push(now);

    }

    double ans = 0;

    while (!st.empty()) {

    Seg now = st.top();

    st.pop();

    ans += (1 - now.x) * (1 - now.x) * now.one + now.x * now.x * now.zero;

    }

    return ans;

}

int main() {

    scanf("%d", &t);

    while (t--) {

    scanf("%d", &n);

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

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

    printf("%.6lf\n", solve(n - 1));

    }

    return 0;

}