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;
}