若存在一个子集s满足答案的话，则该子集一定包含集合S的最大值。 反证法证明： 假设s集合中最大的元素为x，S集合中最大的元素为X。则如果把x换成X，最大值增加了X-x，而平均值增量一定不大于X-x。 这样的话，确定了最大值，s中剩下的数一定从集合S中从小到大依次选取， 而存在一个事实：我们通过不断向集合s中添加元素，集合s的平均值会先减小，后增大。 这个事实可以这样理解：集合s一开始只有X，平均值为X，增加一个元素 a 1 a_1 a1的时候，平均值为 m e a n = ( X + a 1 ) / 2 mean=(X+a_1)/2 mean=(X+a1)/2，变小了，而如果下一个选的元素 a 2 a_2 a2小于mean，那么平均值将变小，否则将变大。由于 a i a_i ai总是递增的，所以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); } } }