題解

若存在一個子集s滿足答案的話，則該子集一定包含集合S的最大值。
反證法證明：
假設s集合中最大的元素為x，S集合中最大的元素為X。則如果把x換成X，最大值增加了X-x，而平均值增量一定不大于X-x。
這樣的話，確定了最大值，s中剩下的數一定從集合S中從小到大依次選取，
而存在一個事實：我們通過不斷向集合s中添加元素，集合s的平均值會先減小，后增大。
這個事實可以這樣理解：集合s一開始只有X，平均值為X，增加一個元素$a_1$的時候，平均值為$mean=(X+a_1)/2$，變小了，而如果下一個選的元素$a_2$小于mean，那么平均值將變小，否則將變大。由于$a_i$總是遞增的，所以mean會先變小后變大。
分析到這里，我們可以得到mean的變化是一個凸函數，可以用三分法求極值點。這樣就做完了。
Notice：這個題有一個特殊的性質，那就是決策點是單調遞增的，直接暴力求解就可以了，用不上三分。
那么為什么決策點是單調遞增的呢？因為最大值是不會變小的的，所以決策點不會變小，仔細思考一下。

---

代碼

上一份三分做的代碼

#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const double inf = 1e18; int Q; int cnt = 0; ll sum[1000000]; double check(int mid,ll x){return double(sum[mid]+x)/double(mid+1); } int main(){cin>>Q;while(Q--){int tp;scanf("%d",&tp);double ans;if(tp == 1){ll x;scanf("%lld",&x);++cnt;sum[cnt] = sum[cnt-1] + x;int l = 0,r = cnt-1,mid,mmid;double mean = inf,tmp;while(r - l > 2){mid = (l+r)/2;mmid = (mid+r)/2;if(check(mid,x) > check(mmid,x)) l = mid;else r = mmid;}double t = min(min(check(l,x),check(r,x)),check((l+r)/2,x));ans = x - t;}else{printf("%.10lf\n",ans);}}}

總結

以上是生活随笔為你收集整理的codefoces 939E Maximize!好题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。