【题解】 LA3708 Graveyard

题目大意

在一个圆周长为10000的圆上等距离分布n个雕塑,现在有m个新加入的雕塑(还是要求等距离摆放),问n个雕塑移动的总距离的最小值.

Solution

显然必然会有一个雕塑不移动,所以可以直接不管他(这个证明的话可以通过代数+中位数证明).

设每一个雕塑移动的距离为\(x_i\),那么显然就是最小化\(\sum_{i=1}^nx_i\)

然后就是直接考虑定一个位置然后把两种情况的都算出来就可以了.

//|--------------------------------|\\

//|author:Biscuit46                |\\

//|mail:[email protected]       |\\

//|Time:2018.10.29 16:33           |\\

//|Link:www.cnblogs.com/Biscuit46  |\\

//|--------------------------------|

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

#define ll long long

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

using namespace std;

inline int gi(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

inline ll gl(){

	ll sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

int main(){

	int i,j,n,m,k;

	while(scanf("%d%d",&n,&m)==2){

		double ans=0.0;

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

			double pos=i*1./n*(n+m);

			ans+=fabs((pos-(floor)(pos+0.5)))/(m+n);

		}

		printf("%.4lf\n",(ans*10000.0));

	}

	return 0;

}