北京微信网站开发,wordpress注册链接,最全的网站大全,印刷网站开发策划书话不多说#xff0c;直接看题#xff1a; 本质是一个数学题#xff1a; 我们令xi0表示反方向传递#xff0c;易得我们就是求每一个xi的绝对值之和min,我们令平均值为a爸。
易得约束条件#xff1a;
x1-x2a1-a,x2-x3a2-a.....
解得x1x1-0,x2x1-((n-1)*a-a2-...an)。…话不多说直接看题 本质是一个数学题 我们令xi0表示反方向传递易得我们就是求每一个xi的绝对值之和min,我们令平均值为a爸。
易得约束条件
x1-x2a1-a,x2-x3a2-a.....
解得x1x1-0,x2x1-((n-1)*a-a2-...an)。。。。
这样就把问题转化成|x1-c1||x2-c2||...|....
又cici1a-ai我们就可以吧c解出来下面是AC代码
#includebits/stdc.h
using namespace std;
const int N1000010;
long long n,a[N];
long long sum0;
long long c[N];
int main(){cinn;for(int i1;in;i){scanf(%lld,a[i]);suma[i];}long long avsum/n;for(int in;i1;i--){c[i]c[i1]av-a[i];}c[1]0;sort(c1,cn1);long long res0;for(int i1;in;i) resabs(c[i]-c[(i1)/2]);coutres;
}
接题 先转换一下我们从小岛的角度来看看看每一个小岛可以被覆盖在x轴上对应的范围这样问题就转换成了给定若干个区间最少选多少个点可以使得每一个区间至少选了一个点。
如何贪心我们先按照右端点排序扫描每一个线段若上一个右端点不在区间那么选右端点。
若在则跳过。
如何严格证明
我们记cnt为算法得到的结果opt为最优解。
显然选了cnt个那么就有cnt个互不相交的区间因此答案一定大于等于cntopt是最优解得证
下面是AC代码
#includebits/stdc.h
using namespace std;
const int N1010;
int n,d;
struct node{double l,r;
}seg[N];
bool cmp(node a,node b){return a.rb.r;
}
int main(){cinnd;bool ff0;for(int i0;in;i){int x,y;scanf(%d%d,x,y);if(yd) ff1;else{double cksqrt(d*d-y*y);seg[i].lx-ck,seg[i].rxck;}}if(ff) cout-1endl;else{sort(seg,segn,cmp);int cnt0;double last-1000000000;for(int i0;in;i){if(lastseg[i].l){cnt;lastseg[i].r;}}coutcnt;}
}
接题 很容易想到假如每一个人的钱都比平均大那么都取平均即可。
假如有一个人少那么让它填满剩下的平均分摊给大于平均的。
下面是严格的证明
我们把方差的每一项看成xi,xi的和为0由均值不等式知我们要让每一个数尽可能相同假如有一个小于平均值假设它不选满则结果肯定变大。
因此若a1平均值那么我们就取a1后面的式子满足加起来和为s-a1,因此剩下的加起来就是s-a1-(n-1)/n*s;此时每一个取到s-a1)/(n-1)是最优的而若此时大于该值那么后面的肯定也大排过序因此取其即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
const int N500100;
int n,a[N];
int main(){long double s;scanf(%d%Lf,n,s);for(int i0;in;i) scanf(%d,a[i]);sort(a,an);long double res0,avs/n;for(int i0;in;i){double curs/(n-i);if(a[i]cur) cura[i];res(cur-av)*(cur-av);s-cur;}printf(%.4Lf\n,sqrt(res/n));
}
