hdu4923 Room and Moor - c++编程基础

TOP

hdu4923 Room and Moor

2015-07-20 17:57:17 来源: 作者: 【大中小】浏览:3次

Tags：hdu4923 Room and Moor

给一个长度为n的A数列，每个数是0或1，要求构造一个递增数列B，长度为n，每个数为[0,1]的实数，使得∑(Ai-Bi)2最小。

可以发现，最前面连续的0和最后面连续的1都没有意义，中间可以看成1和0个数不同的101010串，

对于其中每一个10串，这段B序列取得最佳值是 1的个数/总个数，

每次添加取一段，如果这一段的最佳值小于上一段的取值，那么就把两段合起来更新一个新的最佳值，然后再往前比较，直到满足递增序列位置。

看了别人代码发现，这样想是对的，在处理的时候其实不用分10段，直接逐个处理是一样的。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        using namespace std; double x,s[100010][2]; int main() { int icy,n,cnt,i; scanf("%d",&icy); while(icy--) { scanf("%d",&n); cnt=0; for(i=0;i
        
         =2) { if(s[cnt-1][0]/s[cnt-1][1]>=s[cnt-2][0]/s[cnt-2][1]) break; s[cnt-2][0]+=s[cnt-1][0]; s[cnt-2][1]+=s[cnt-1][1]; cnt--; } } double ans=0; for(i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1905（二分）	下一篇：POJ2352_Stars(线段树/单点更新)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: