本文从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 |
|
uva 11300 Spreading the Wealth
题意:有n个围着坐成一圈,每个人手上有点数,n个人的点数之和可以被n整除,每个人可以把自己的点数给一部分给相邻的两个人,没给一点计数一次,最后令所有人的点数相同,使得计数最少
- 假设最后每个人手上的点数为平均数ave
- 一开始每个人手上的点数为ai
- 设gi为第i个人给第i+1个人gi点数(gi > 0 , 第i个人给第i+1人 , gi < 0 , 第i+1个人给第i个人);特别地,gn表示第n个人给第1个人的点数
- 对于第i个人,最终数量都是 ave,且 ave = ai - gi + gi-1
特别地,对于第1个人,ave = a1 - g1 + gn - 我们要求的,其实就是 ans = min{ |g1| + |g2| + |g3| + ……. + |gn| }
想办法表示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
最终答案:
1
2
3ans = 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 |
|