首页 > 代码库 > HDU 4923 Room and Moor

HDU 4923 Room and Moor

2024-07-16 21:07:30   219人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4923

解题报告：给出一个长度为n的只包含0和1的序列，是否存在一个序列Bi满足一下条件：

1.           0 <= B[i] <= 1

2.          B[i] <= B[i+1]

3.          f(A,B) = ∑(i=1-n) (A[i] - B[i])^2 

4.          f(A,B)最小是多少 

前面的0可以直接去掉，后面的1可以直接去掉，然后剩下中间形如1 1 0 0的序列，在这样的区间中前后的B[i]很明显应该是相等才能保证最小的，

我们可以先分别求出每段这样的区间的B[i]，然后维护一个单调队列，当要插入的B[i]大于等于队尾的B[i]，则直接插入，当要插入的小于队尾的B[i],

则将队尾的那个区间跟现在要插入的区间合并然后求出一个新的B[i]代替，得到新的B[i]之后注意又要跟队尾比较。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<deque> 6 using namespace std; 7 #define maxn 100005 8 struct node 9 {10     int a,b;11     double x;12 }B[maxn];13 int A[maxn];14 deque<node> que;15 int main()16 {17     int T,n;18     scanf("%d",&T);19     while(T--)20     {21         scanf("%d",&n);22         for(int i = 1;i <= n;++i)23         scanf("%d",&A[i]);24         while(n >= 1 && A[n] == 1)  //把后面的1去掉 25         n--;26         int s = 1;27         while(s <= n && A[s] == 0)28         s++;29         if(s >= n)30         {31             printf("%.6lf\n",0);32             continue;33         }34         A[0] = 0;35         int f = 0;36         for(int i = s;i <= n;++i)37         {38             if(A[i] == 1)39             {40                 if(A[i-1] == 0 && A[i] == 1)41                 {42                     f++;43                     B[f].a = B[f].b = 0; //初始化 44                     45                 }46                 B[f].a++;47             }48             else B[f].b++;49             50         }51         for(int i = 1;i <= f;++i)   //遍历一遍，计算出每节的x应该是多少 52         B[i].x = (double)B[i].a / (double)(B[i].a + B[i].b);53         54     //    for(int i = 1;i <= f;++i)55     //    printf("a = %d b = %d  x = %.6lf\n",B[i].a,B[i].b,B[i].x);56         que.clear();57         node temp;58         deque<node>::iterator iter;59         for(int i = 1;i <= f;++i)        //维护一个单调队列 60         {61             if(que.empty() || B[i].x >= que.begin()->x)62             que.push_front(B[i]);63             else64             {65                 while(!que.empty() && B[i].x < que.begin()->x)66                 {67                     B[i].a += que.begin()->a;68                     B[i].b += que.begin()->b;69                     B[i].x = (double)B[i].a / (double)(B[i].a + B[i].b);70                     que.pop_front();71                 }72                 i--;  //为了在下一次循环中，把这个节点插入到队列中 73             }74         }75         double tot = 0;76         for(iter = que.begin();iter != que.end();++iter)77         tot += ((double)iter->a * (1.0 - iter->x) * (1.0 - iter->x) + (double)iter->b * iter->x * iter->x);78         printf("%.6lf\n",tot);79     }80     return 0;81 }
View Code

 


联系
我们