首页 > 代码库 > hdu4923 Room and Moor
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 <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> 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<n;i++) { scanf("%lf",&x); s[cnt][0]=x; s[cnt++][1]=1; while(cnt>=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<cnt;i++) { double tmp=s[i][0]/s[i][1]; ans+=(tmp*tmp*(s[i][1]-s[i][0])+(1-tmp)*(1-tmp)*s[i][0]); } printf("%.6lf\n",ans); } return 0; }
hdu4923 Room and Moor
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。