UVA 1388 11300 两道数学分析题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

uva 1388 Graveyard

题意：一个圆形，周长为10000，一开始有n个点，在圆周上等距分布，新插入m个点，使得n+m个点也等距分布，那么可能要移动一些点才能达到目的，求所有点移动的位移和最小

设n个点的时候两两点间距为d1，任意取一个点P，放在x轴的0点上，然后顺时针把n个点取下来依次放在x轴的d1，2d1,3d1,4d1………………处，把这些点标号为a0,a1,a2…..an

设n+m个点的时候两两点间距为d2，除下P放在x轴0点上，然后顺时针把n+m个点取下来依次放在x轴的d2,2d2,3d2,4d2…………..把这些点标号为b0,b1,b2….bn+m
我们只需要调整之前的n个点即可，调整好了，新进来的m个点是直接放在合适的位置的，不需要移动

其实就是把ai调整到合适的bj上，那当然是选离ai最近的bj

问题是，会不会有两个点ai，ai+1放在同一个bj上呢？

a0和b0的坐标都是0，所以a0放在b0上，而b1肯定在a0和a1之间（d2 < d1），所以a1距离b1的距离肯定近过b0，a1只可能放在b1和b2上，不可能放在b0上，所以i = 0的情况不成立
对于i > 0 , 假设距离ai和ai+1最近的点都是bj，那么可知，bj一定是在ai和ai+1之间
假设bj在ai和ai+1中点处

ai坐标为(i-1) d1, ai+1坐标为i d1, bj坐标为(i-1) * d1 + d1/2

那么bj+1的坐标就为 bj+1 = bj + d2 = (i-1) * d1 + d1/2 + d2

因为 d2 < d1 所以 bj+1 = (i-1) d1 + d1/2 + d2 < (i-1) d1 + d1/2 + d1 = i * d1 + d1/2 = ai+1 + d1/2

bj+1 < ai+1 + d1/2

bj = ai + d1/2 = ai+1 - d1/2

可见bj+1距离ai+1更近，ai+1应该放在bj+1而不是放在bj，与假设矛盾

同理，即使假设bj在ai和ai+1之间的任意一个地方，也可以证明假设是不成立的

所以可知，ai一定唯一对应一个bj，只要暴力找出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
#define N 1010

double a[N],b[N+N];

int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		double d;
		d = 1.00 * 10000 / n;
		a[0] = 0.0;
		for(int i = 1; i < n; i++)
			a[i] = a[i-1] + d;
		d = 1.00 * 10000 / (n+m);
		b[0] = 0.0;
		for(int i = 1; i < n+m; i++)
			b[i] = b[i-1] + d;
		double ans = 0.0;
		for(int i = 0; i < n; i++){
			double Min = 10000000.0;
			for(int j = 0; j < n+m; j++){
				d = fabs(a[i] - b[j]);
				Min = min(Min,d);
			}
			ans += Min;
		}
		printf("%.4lf\n",ans);
	}
	return 0;
}

uva 11300 Spreading the Wealth

题意：有n个围着坐成一圈，每个人手上有点数，n个人的点数之和可以被n整除，每个人可以把自己的点数给一部分给相邻的两个人，没给一点计数一次，最后令所有人的点数相同，使得计数最少

  1. 假设最后每个人手上的点数为平均数ave
  2. 一开始每个人手上的点数为ai
  3. 设gi为第i个人给第i+1个人gi点数（gi > 0 , 第i个人给第i+1人 ， gi < 0 , 第i+1个人给第i个人）；特别地，gn表示第n个人给第1个人的点数
  4. 对于第i个人，最终数量都是 ave，且 ave = ai - gi + gi-1
    特别地，对于第1个人，ave = a1 - g1 + gn
  5. 我们要求的，其实就是 ans = min{ |g1| + |g2| + |g3| + ……. + |gn| }

  6. 想办法表示gi：设第i个人的调整量为ci，ci = ave - ai = gi-1 - gi

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    特别地，
    c1 = gn - g1
    c1 = gn - g1
    c2 = g1 - g2
    c3 = g2 - g3
    ...........
    cn = gn-1 - gn
    ----->
    g1 - gn - c1
    g2 = gn - (c1+c2)
    g3 = gn - (c1+c2+c3)
    ........
    gn-1 = gn - (c1+c2+c3....+cn-1)

    留意到 c1+c2+c3….+cn = gn - gn = 0，这是恒成立，因为所有点的调整量之和是0

    根据上面，我们就可以用gn来表示所有的gi

    设si = c1+c2+….ci

    gi = gn - si

  7. 最终答案：

    1
    2
    3
    ans = min{ |g1| + |g2| + |g3| + ....... + |gn| }
       	 = min{ |gn-s1| + |gn-s2| + |gn-s3| + ........ + 
       	 		 |gn-sn-1| + |gn-0|};
注意s1到sn-1不是递增或递减的，因为ci并不一定都是是正数或负数，但并不影响这个函数的性质

把< 0，s1，s2，s3......sn-1 >排序之后，更方便理解这个函数，这个函数是“V”型的，随着gn增大，值变小，gn再增大，值变大，所以当gn = <0,s1,s2,s3.....sn-1>的中位数的时候，整个函数取最小值

得到了gn，就可以 得到ans了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL long long
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 1000010

LL  a[N],c[N],s[N],temp[N],ave,sum;

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		sum = 0LL;
		for(int i = 1; i <= n; i++){
			scanf("%lld",&a[i]);
			sum += a[i];
		}
		ave = sum / n;
		s[0] = 0LL;
		c[1] = ave - a[1];
		s[1] = c[1];
		for(int i = 2; i < n; i++){
			c[i] = ave - a[i];
			s[i] = s[i-1] + c[i];
		}
		copy(s,s+n,temp);
		sort(temp,temp+n);
		LL gn = temp[(n-1)/2];
		LL ans = 0LL;
		for(int i = 1; i < n; i++){
			ans += abs(gn - s[i]);
		}
		ans += abs(gn);
		cout << ans << endl;
	}
	return 0;
}