題意：

給一個(gè)0和1組成的序列a，要構(gòu)造一個(gè)相同長度的序列b。b要滿足非嚴(yán)格單調(diào)，且

值為0到1的實(shí)數(shù)。最后使得 ?sum((ai-bi)^2)最小。

算法：

首先a序列開始的連續(xù)0和末尾的連續(xù)1是能夠不考慮的。

由于僅僅要b序列相應(yīng)開頭為0、

末尾為1，既不影響單調(diào)性又能使相應(yīng)的（ai-bi)^2=0。

然后，

先找111100、11100、10這樣以1開始以0結(jié)束的序列塊。每一塊相應(yīng)的b值相等且均為

這一塊的平均值，即1的個(gè)數(shù)/0和1的總個(gè)數(shù)。

可是要滿足b的單調(diào)性，則我們用棧來維護(hù)，假設(shè)后面一塊的均值<前面一塊的均值，則

合并這兩塊。也就是僅僅要棧頂?shù)膲K的均值小于要壓入棧的塊的均值，就一直合并，直到

滿足單調(diào)性。再把當(dāng)前的值壓入棧。

最后僅僅要一塊塊統(tǒng)計(jì)相應(yīng)的sum((ai-bi)^2)就是答案了。

逗逼記憶---->比賽的時(shí)候我沒有想到塊，僅僅想到除去前面的0和后面的1。中間的值都是一樣。

用二分或者三分解決，僅僅要控制精度=。

=

P.S: ? 這題必須注意細(xì)節(jié)，否則極易丟失精度。主要是我代碼凝視的兩個(gè)我開始沒有控制好的地方。

o(╯□╰)o

#include<cstdio> #include<iostream> #include<cstring> #define maxn 100010 using namespace std;struct node {double num,v; //v表示1的個(gè)數(shù),num表示0和1的總個(gè)數(shù) }; node stk[maxn]; double sum[maxn],a[maxn];int main() {int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++){scanf("%lf",&a[i]);sum[i] = sum[i-1]+a[i];}int i = 1,k = n;while(a[i]==0) i++;while(a[k]==1) k--;int top = 0,le = i;node x,y;for(;i<=k;i++){if(a[i]==0){while(a[i]==0 && i<=k) //這里假設(shè)不加控制i<=k,i可能超出ki++;double a = sum[i-1]-sum[le-1];double b = (double)i-le;while(top>0 && a/b<stk[top].v/stk[top].num) //這里也不能忘了top>0{y = stk[top--];a += y.v;b += y.num;}x.v = a;x.num = b;stk[++top] = x;le = i;}}double ans = 0;while(top){y = stk[top--];double val = y.v/y.num;ans += (1-val)*(1-val)*y.v + val*val*(y.num-y.v);}printf("%.6lf\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 4923 Room and Moor (单调栈+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。