程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4923 Room and Moor(瞎搞題)

HDU 4923 Room and Moor(瞎搞題)

編輯：C++入門知識

HDU 4923 Room and Moor(瞎搞題)

瞎搞題啊。找出1 1 0 0這種序列，然後存起來，這種情況下最好的選擇是1的個數除以這段的總和。然後從前向後掃一遍，變掃邊進行合並。每次合並，合並的是他的前驅。這樣到最後從t-1找出的那條鏈就是最後滿足條件的數的大小。

Room and Moor

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 307 Accepted Submission(s): 90

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:

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

Source 2014 Multi-University Training Contest 6

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-9
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) scanf("%d",&num[i]);
        int t = 0;
        int cnt1 = 0;
        int cnt2 = 0;
        if(!num[0]) cnt1 = 1;
        if(num[0]) cnt2 = 1;
        for(int i = 1; i < n; i++)
        {
            if(num[i] > num[i-1])
            {
                sum[t][0] = cnt1;
                sum[t++][1] = cnt2;
                cnt1 = cnt2 = 0;
                if(!num[i]) cnt1++;
                if(num[i]) cnt2++;
                continue;
            }
            if(!num[i]) cnt1++;
            if(num[i]) cnt2++;
        }
        sum[t][0] = cnt1;
        sum[t][1] = cnt2;
        t++;
        for(int i = 0 ; i < t; i++) x[i] = (1.0*sum[i][1]/((sum[i][0]+sum[i][1])*1.0));
        pre[0] = -1;
        for(int i = 1; i < t; i++)
        {
            if(x[i] < x[i-1])
            {
                sum[i][0] += sum[i-1][0];
                sum[i][1] += sum[i-1][1];
                x[i] = 1.0*sum[i][1]/(sum[i][1]+sum[i][0])*1.0;
                pre[i] = pre[i-1];
                int p = pre[i];
                while(p != -1)
                {
                    if(x[i] < x[p])
                    {
                        sum[i][0] += sum[p][0];
                        sum[i][1] += sum[p][1];
                        x[i] = 1.0*sum[i][1]/(sum[i][0]+sum[i][1])*1.0;
                        pre[i] = pre[p];
                        p = pre[p];
                        continue;
                    }
                    break;
                }
                continue;
            }
            pre[i] = i-1;
        }
        int p = pre[t-1];
        double ans =0;
        ans += sum[t-1][0]*pow(x[t-1], 2)+sum[t-1][1]*pow(x[t-1]-1, 2);
        while(p != -1)
        {
            ans += sum[p][0]*pow(x[p], 2)+sum[p][1]*pow(x[p]-1, 2);
            p = pre[p];
        }
        printf("%.6lf\n",ans);
    }
    return 0;
}