无锡网站制作优化,介绍公司的文案,免费开源商城系统源码,门户网站大全题解 若存在一个子集s满足答案的话#xff0c;则该子集一定包含集合S的最大值。 反证法证明#xff1a; 假设s集合中最大的元素为x#xff0c;S集合中最大的元素为X。则如果把x换成X#xff0c;最大值增加了X-x#xff0c;而平均值增量一定不大于X-x。 这样的话#xff0…题解 若存在一个子集s满足答案的话则该子集一定包含集合S的最大值。 反证法证明 假设s集合中最大的元素为xS集合中最大的元素为X。则如果把x换成X最大值增加了X-x而平均值增量一定不大于X-x。 这样的话确定了最大值s中剩下的数一定从集合S中从小到大依次选取 而存在一个事实我们通过不断向集合s中添加元素集合s的平均值会先减小后增大。 这个事实可以这样理解集合s一开始只有X平均值为X增加一个元素a1a_1a1的时候平均值为mean(Xa1)/2mean(Xa_1)/2mean(Xa1)/2变小了而如果下一个选的元素a2a_2a2小于mean那么平均值将变小否则将变大。由于aia_iai总是递增的所以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(mid1);
}
int main(){cinQ;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 (lr)/2;mmid (midr)/2;if(check(mid,x) check(mmid,x)) l mid;else r mmid;}double t min(min(check(l,x),check(r,x)),check((lr)/2,x));ans x - t;}else{printf(%.10lf\n,ans);}}}
