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

给一个长度为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