LA3708 NEERC2006 墓地雕塑

题意:给你一个10000的圆,一开始有n个点均等排在上面,考虑加入m个点,然后使得(n+m)等分,问你最少移动这n个点多少距离. 思路:对于每一个原来的n个点来说,一定有其中的一个点是不用动的.那么其他的点就要移动到它最近的(n+m)等分的点上去. 事实上,把圆圈展开成一条直线,就可以看作有(n)等分点与一个点在起点.现在新增了(n+m)个等分点,我们只需要从前往后扫描,每个点移动到对应的位置即可. 我们设这条直线长度为L(也就是周长C) 但问题出现了,在这样做的过程中,是否会使得某些位置没有被使用,但是雕塑却又放不进去呢.也就是为了距离最短,放弃使用一些远的位置,而造成了某些点没有位置放置呢. 在编写了一段证明后发现无法严格地去证明,但凭直觉,在添加了m个点后,整个线段比原来会多出更多的坑位,而且位移的距离不会太大.因为在规模较大时,n等分点与n+m等分点几乎重合了. 现在只用考虑会不会有两个点重叠在了一起,我认为不会,因为n等分点间应当有相当数量的点,若仅有一个,也可以考虑两边的点. 总的来说这题也是非常巧妙,利用了坐标缩放 每一个n个点的坐标缩放为： i ∗ ( n + m ) / n i*(n+m)/n i∗(n+m)/n,每一个坑的位置是0,1,2,3…n-1 那么我们要找最近的坑 事实上就是在做四舍五入.比如说如果第i个点的坐标是4.2,那么它就应当去找4,如果是4.7就该去找5.那么距离的贡献就 ∣ a − f l o o r ( a + 0.5 ) ∣ |a-floor(a+0.5)| ∣a−floor(a+0.5)∣,其中floor+0.5是四舍五入 代码: 为什么只能是PE奶奶的…

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 3e5+2;
const int INF = 1e9+7;
typedef pair pii;
int main(){
//	freopen("1.txt","r",stdin);
	int n,m;
	while(scanf("%d %d",&n,&m)==2){
		double ans = 0.0;
		for(int i=1;i