话不多说，直接看题：

本质是一个数学题：

我们令xi<0表示反方向传递，易得我们就是求每一个xi的绝对值之和min,我们令平均值为a爸。

易得约束条件：

x1-x2=a1-a,x2-x3=a2-a.....

解得x1=x1-0,x2=x1-((n-1)*a-a2-...an)。。。。

这样就把问题转化成|x1-c1|+|x2-c2|+|...|....

又ci=ci+1+a-ai我们就可以吧c解出来，下面是AC代码：

#include

using namespace std;

const int N=1000010;

long long n,a[N];

long long sum=0;

long long c[N];

int main(){

cin>>n;

for(int i=1;i<=n;i++){

scanf("%lld",&a[i]);

sum+=a[i];

}

long long av=sum/n;

for(int i=n;i>1;i--){

c[i]=c[i+1]+av-a[i];

}

c[1]=0;

sort(c+1,c+n+1);

long long res=0;

for(int i=1;i<=n;i++) res+=abs(c[i]-c[(i+1)/2]);

cout<

}

接题：

先转换一下，我们从小岛的角度来看，看看每一个小岛可以被覆盖在x轴上对应的范围，这样问题就转换成了给定若干个区间，最少选多少个点可以使得每一个区间至少选了一个点。

如何贪心？我们先按照右端点排序，扫描每一个线段，若上一个右端点不在区间，那么选右端点。

若在则跳过。

如何严格证明？

我们记cnt为算法得到的结果，opt为最优解。

显然选了cnt个，那么就有cnt个互不相交的区间，因此答案一定大于等于cnt+opt是最优解，得证！

下面是AC代码：

#include

using namespace std;

const int N=1010;

int n,d;

struct node{

double l,r;

}seg[N];

bool cmp(node a,node b){

return a.r

}

int main(){

cin>>n>>d;

bool ff=0;

for(int i=0;i

int x,y;

scanf("%d%d",&x,&y);

if(y>d) ff=1;

else{

double ck=sqrt(d*d-y*y);

seg[i].l=x-ck,seg[i].r=x+ck;

}

}

if(ff) cout<<-1<

else{

sort(seg,seg+n,cmp);

int cnt=0;

double last=-1000000000;

for(int i=0;i

if(last

cnt++;

last=seg[i].r;

}

}

cout<

}

}

接题：

很容易想到，假如每一个人的钱都比平均大，那么都取平均即可。

假如有一个人少，那么让它填满，剩下的平均分摊给大于平均的。

下面是严格的证明：

我们把方差的每一项看成xi,xi的和为0，由均值不等式知我们要让每一个数尽可能相同，假如有一个小于平均值，假设它不选满，则结果肯定变大。

因此，若a1<平均值，那么我们就取a1，后面的式子满足加起来和为s-a1,因此剩下的加起来就是s-a1-(n-1)/n*s;此时每一个取到（s-a1)/(n-1)是最优的，而若此时大于该值，那么后面的肯定也大（排过序），因此取其即可。

下面是AC代码：

#include

using namespace std;

const int N=500100;

int n,a[N];

int main(){

long double s;

scanf("%d%Lf",&n,&s);

for(int i=0;i

sort(a,a+n);

long double res=0,av=s/n;

for(int i=0;i

double cur=s/(n-i);

if(a[i]

res+=(cur-av)*(cur-av);

s-=cur;

}

printf("%.4Lf\n",sqrt(res/n));

}

文章链接

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：