题目链接：?pid=4923题目大意：给一个0 1序列，要求构造一个实数序列，(要求bi属于[0, 1]且bi单调递增(非严格递增)) 使得(ai – bi)^2的和最小，输出这个结果题目分析：首先原来0 1序列的最前面的连续0和最后面的连续1可以忽略，因为序列b中可以构造对应的0 1，使其差为0，接着我们取剩下序列中形如10，1100。。。的子序列，即连续1加上连续0的子序列，尽可能让每一个这样的子序列构造出的结果最小，策略显然是尽量取平均！比如最简单的1100，我们构造的bi对应的值应该是0.5 0.5 0.5 0.5，假设子序列有c0个0，c1个1，平均值为val，则val = (c1 * 1 + c0 * 0) / (c0 + c1)，因此我们可以得到val为c1 / (c0 + c1)，然后维护一个单调栈即可，当当前的val比栈顶的val小时，取出栈顶元素，将这段序列与栈顶序列中和，再入栈，中和的方式就是重新计算val值，，最后将栈中的元素纷纷弹出并累计c1 * (1 – val)^2 + c0 * val^2比如样例1：1 1 1 1 1 0 0，val = 5 / 7，则ans = 5 * (1 – 5/7)^2 + 2 * (5/7)^2 #include <cstdio>#include <cstring>#include <stack>using namespace std;int const MAX = 1e5 + 5;struct DIVIDE{int c0, c1;double val;}d[MAX];int a[MAX];stack <DIVIDE> stk;int main(){int T, n;scanf("%d", &T);while(T–){double ans = 0;memset(a, 0, sizeof(a));scanf("%d", &n);int st = 1, ed = n;for(int i = 1; i <= n; i++)scanf("%d", &a[i]);while(ed >= 1 && a[ed] == 1)ed –;while(st <= n && a[st] == 0)st ++;int cnt = 0;for(int i = st; i <= ed; i++){if(a[i] == 1){if(a[i – 1] == 0){cnt ++;d[cnt].c0 = d[cnt].c1 = 0;}d[cnt].c1 ++;}elsed[cnt].c0 ++;}for(int i = 1; i <= cnt; i++)d[i].val = (d[i].c1 * 1.0) / ((d[i].c1 + d[i].c0) * 1.0);for(int i = 1; i <= cnt; i++){if(stk.empty() || d[i].val >= stk.top().val)stk.push(d[i]);else{while(!stk.empty() && d[i].val < stk.top().val){d[i].c0 += stk.top().c0;d[i].c1 += stk.top().c1;d[i].val = (d[i].c1 * 1.0) / ((d[i].c1 + d[i].c0) * 1.0);stk.pop();}i –;}}while(!stk.empty()){int c1 = stk.top().c1;int c0 = stk.top().c0;double val = stk.top().val;ans += c1 * (1.0 – val) * (1.0 – val) + c0 * val * val;stk.pop();}printf("%.6f\n", ans);}}
我想去旅行，一个人背包，一个人旅行，
