hdoj 4923 Room and Moor

川长思鸟来 2022-08-10 17:50 101阅读 0赞

题目：[hdoj 4923 Room and Moor ][hdoj 4923 Room and Moor]

来源：[2014 Multi-University Training Contest 6][]

题意：给出一个只有1和0组成的序列A，让你构造一个递增的序列B,满足让 求和（AI-BI）^2 尽可能的小。

**分析：分析发现，前面连续的0和后面连续的1是不影响结果的，而对于某一段，我们假设1的个数为x，0的个数为y，我们列式化简之后发现所求值为（x\*y）/（x+y）。观察这个等式发现 0 和 1 的个数互换是不影响结果的，但是他会影响我们下面的选择，对于某一段我们要构造的数是 x / （x+y），而题意要求这个序列必须是递增的，那么我们可以通过一次遍历构造出这个递增的序列，当不满足递增时我们累加到前面一个，最后对构造出来的序列就和就ok，发现这样构造的话前面的0和后面的1正好不影响结果。**

**代码：**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn = 100005;
    
    double num[maxn], len[maxn];
    
    int main()
    {
    	int t, n;
    	scanf("%d", &t);
    	while (t--)
        {
    		scanf("%d", &n);
    		int cnt = 0, a;
    		for (int i = 0; i < n; i++)
    		{
    			scanf("%d", &a);
    			num[cnt] = a;
    			len[cnt++] = 1;
    			while (cnt >= 2)
    			{
    				if (num[cnt-1]/len[cnt-1] > num[cnt-2]/len[cnt-2])
    					break;
    				num[cnt-2] += num[cnt-1];
    				len[cnt-2] += len[cnt-1];
    				cnt--;
    			}
    		}
    		double ans = 0.0;
    		for (int i = 0; i < cnt; i++) {
    			double tmp = num[i]/len[i];
    			ans += num[i]*(len[i]-num[i])/len[i];
    		}
    		printf("%.6lf\n", ans);
    	}
    	return 0;
    }

[hdoj 4923 Room and Moor]: http://acm.hdu.edu.cn/showproblem.php?pid=4923
[2014 Multi-University Training Contest 6]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014%20Multi-University%20Training%20Contest%206&source=1&searchmode=source