首页 > 代码库 > HDU 4923 Room and Moor(推理+栈维护)
HDU 4923 Room and Moor(推理+栈维护)
HDU 4924 Room and Moor
题目链接
题意:给定一个01组成的a序列,要求一个b序列,b序列每个数值为[0, 1]之间的数,并且b序列为非递减序列,要求∑(ai?bi)2最小,求这个最小值
思路:推理,很容易看出,开头一段的0和末尾一段的1等于没有,然后中间每段类似111000这样1在前,0在后的序列,都可以列出一个公式,很容易推出选择的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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。