带权中位数 学习笔记

By | 02月01日
Advertisement

【线性模型】

(一)不带权中位数

在一条直线上给出若干点,要求求出直线上的一点使其他所有点到这个点的距离之和最小。

我们会发现按照这些点的坐标排序了之后,答案即为最中间的那个点(若中间有两个点则两个点均可)。怎样来证明呢?

首先证明所求点一定可以表示为给出点中的一个

带权中位数 学习笔记

设所求的点的坐标为x,设所有L左边的人走到L的距离总和为A,所有R右边的人走到R的距离总和为B,那么易知:

若A>B,要使x-L尽可能的小,那么x应与L重合;

若A<B,要是R-x尽可能的下,那么x应与R重合;

若A=B,x在区间[A,B]内任何点对答案均无影响。

得出:x一定可以用一个已知点表示。

由此也可得出,如果点数为偶数,选取最中间的两个点都为最小值。

接着证明x点为按横坐标排序后的中点

带权中位数 学习笔记

容易知道:x一定在任意两点之间。

只看L,R,x这三个点,如果x在LR之间,那么LR到x的距离之和即为LR两点的距离;如果x在LR之外,那么距离值和一定大于LR的距离,也就是说不可能再优。同理可知,x必须在任意两点之间,又由上面已证的结论知道,x即为最中间的一点或两点。

(二)带权中位数

接着上面的题目,如果每个人都有一个权值,它们移动到一点的花费为距离与权值的乘积,那么这个时候怎么选点使总花费最小呢?

其实权值就可以看成是这个点上总的人数,仍然要找所有人的中点。那么这个问题就转化为了按坐标排序后,从一段扫描,把扫描过的点的权值相加记为sum。一旦遇到了一个点加上之后sum大于了总权值的一半,那么这个点就是所求的点。

也给出另外一种证明:

我们可以简单地把上面的证明过程看作是左边的人都集合到了M点,而右边的人都集合到了M+1点。此时形成了两军对垒的形式,如果左边的总人数比右边的多,那么从左边走到右边去就没有从右边走到左边来优,反之亦然。那么既然在当前点我们左边的总人数已经比右边多了,那么再往右边移动,左边的人数会进一步增多,而右边的人会减少,那么只会导致更差的结果,所以此时我们可以判断最优点一定在当前点的左边,或者至少在当前这个点。那么范围就从当前的[L,R]缩小到了[L,M],通过不断地缩小范围(而每一次缩小我们都砍掉了一半的范围),最后我们得到的将是一个点——那就是我们要求的集合位置。

下面是百度上的数学证明方法:

若最优点在T

则有:

{D[I]*DIST(I,T)}(I<>T)<={D[I]*DIST(I,T+1)}(I<>T+1)

将此式化为:

{D[L]}*DIST(L,T)}+{D[R]*DIST(R,T)}+D[T+1]*DIST(T+1,T)

<=∑{D[L]}*DIST(L,T+1)}+∑{D[R]*DIST(R,T+1)}+D[T]*DIST(T,T+1) (L<T&R>T+1)

即:

{D[L]*DIST(L,T+1)}-{D[L]*DIST(L,T)}(L<T)+D[T]*(DIST(T,T+1))>={D[R]*DIST(R,T)}-(D[R]*DIST(R,T+1))(R>T+1)+D[T+1]*(DIST(T,T+1))进一步化简为:

{D[L]*(DIST(L,T)-DIST[L,T+1])}(L<=T)<={D[R]*(DIST(R,T+1)-DIST(R,T))}(R>=T+1)DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)

DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)

OBVIOUSLY : DIST(T,T+1)=DIST(T+1,T)

因此:

D[L](L<=T)>=(D[R])(R>=T+1)

即:∑D[L](L<T)+D[T]>=(D[R])(R>T)

因此我们发现,若T是最优点,则必有其左边的权值和加上D[T]后大于右边的权值和

而类似的,我们可以证明其右边的权值和加上D[T]后大于左边的权值和

因此我们要找的点也就是满足以上条件的点。注意到此时我们的选择已经和具体的位置(坐标)没有关系了,而成为主要考虑因素的仅仅是各点上的权值。

因为左边的权值和数+D[T]>=右边的权值和,那么:

LEFTSUM+D[T]>=RIGHTSUM=SUMALL-(LEFTSUM+D[T])

=>2*(LEFTSUM+D[T])>=SUMALL

=>2*RIGHTSUM<=SUMALL

同理可得:

RIGHTSUM+D[T]>=LEFTSUM=SUMALL-(RIGHTSUM+D[T])

=>2*(RIGHTSUM+D[T])>=SUMALL

=>2*LEFTSUM<=SUMALL

此时我们发现:

2*LEFTSUM<=SUMALL 2*(LEFTSUM+D[T])>=SUMALL

也即是说当前的位置T上的数包含了第[(SUMALL)/2]个数,由开篇的简述可知,这第[(SUMALL)/2]个数,就是这个序列中的带权中位数。所以这一类问题,实质上就是带权中位数问题。

【坐标型模型】

明白了线性模型之后,带权中位数也可以推广到平面直角坐标系中。

(一)如果坐标系中有一些带权点,需要你找一条平行于x轴或平行于y轴的直线,使所有的点到直线的距离乘以各自的权值的总和最小。

只是这类问题就可以想象成是线性模型。由于直线是平行或垂直于x轴的,所以各点的横坐标(或纵坐标)不用考虑。那么就只按照横坐标(或纵坐标)排序然后按照之前的方法求值即可。

(二)如果坐标系中有一些带权点,需要你找一个点,使所有的点到这个点的距离乘以各自的权值的总和最小。(距离表示为ABS(x-x1)+ABS(y-y1))

其实我们知道这道题中的横纵坐标是不会互相干扰的,也就是说,求出(一)中所求出的两条直线的交点即为所求的点。证明不再给出

【总结】

带权中位数问题其实是一类比较简单的问题,在信息学竞赛中常有应用。

Similar Posts:

  • 【带权中位数】【120715测试】【朱全明NOIP模拟题】YL杯超级篮球赛

    样例输入输出 ball.in 1 1 0 0 ball.out 0.00 这是一道有关带权中位数(http://www.cnblogs.com/oijzh/articles/2647134.html)的题 分析题目不难发现,xy坐标是不相关的,所以应该离散化分开来,并且最终的目标位置必定在某一个人的点上(如果不在某一个点上,那么必定可以把这个点向左或向右移来找到一个更优的位置!) 了解了带权中位数,这道题就很好做了 Pascal Code program ball; type arr=array

  • 【带权中位数】科研先行(research)

    科研先行(research) 输入文件:research.in 输出文件:research.out [问题描述] Neyc绿化破坏电信事件,给领导层造成了很大的麻烦.为避免类似事件发生,领导意识到,做任何事情,科研必须先行.为此,Neyc专门成立了研究所,对Neyc的整体建设进行研究设计.研究所计划从全国各地邀请相关专家集中研讨.因为每个地区邀请的人数不同,出于节约经费的问题,Neyc研究所希望集中讨论的时候能尽量花费较少的费用.于是,就出现了一个集中地点的选择问题. 假设被邀请参与研究人员所在

  • android自带示例notepad学习笔记一

    app主要功能: 1):显示用户以前写下的note; 2):修改note; 3):修改note title; 4):删除note 5)粘贴 app设计: 用户能够交互的界面主要有三个NoteList ,TitleEditor 与 NoteEditor. NoteList:列出note,根据操作跳转到NoteEditor或TitleEditor.代码为 NoteList.java. NoteEditor:修改note内容.代码为NoteEditor.java. TitleEditor:修改note

  • EM算法学习笔记_2(opencv自带EM sample学习)

    实验说明: 在上一讲EM算法学习笔记_1(对EM算法的简单理解) 中已经用通俗的语言简单的介绍了下EM算法,在这一节中就采用opencv自带的一个EM sample来学习下opencv中EM 算法类的使用,顺便也体验下EM 算法的实际应用. 环境:Ubuntu12.04+Qt4.8.2+QtCreator2.5+opencv2.4.2 在这里需要使用2个与EM算法有关的类,即CvEM和CvEMParams,这2个类在opencv2.4.2已经放入legacy文件夹中了,说明不久就会被淘汰掉,因为

  • cocos2d-x入门学习笔记,主要介绍cocos2d-x的基本结构,并且介绍引擎自带的示例

    cocos2d-x 3.0 制作横版格斗游戏 http://philon.cn/post/cocos2d-x-3.0-zhi-zuo-heng-ban-ge-dou-you-xi http://blog.csdn.net/start530/article/category/1295763 介绍入门ok http://blog.csdn.net/column/details/cocos2d-x-study.html cocos2d-x入门学习笔记,主要介绍cocos2d-x的基本结构,并且介绍引擎

  • struts2自带项目showcase的tags学习笔记

    struts2自带项目showcase的tags学习笔记 第一.首先我们来看non-ui的标签. 有几个需要注意的地方: 1.actionTag <s:action name="includePage" namespace="/tags/non-ui/actionTag" executeResult="true" /> 这里的action并不是存在于url或是form中,而是直接一个单独的标签,这里的executeResult为tru

  • struts2自带项目showcase的fileupload与filedownload功能学习笔记

    struts2自带项目showcase的fileupload功能学习笔记 学习Struts2的自带项目showcase的fileupload功能.把我认为的一些疑问点写下来. 第一.我们先理解下struts-xml中的package的namespace属性,这个属性自然是为了在不同的命名空间中可以使用同名的action.我们先看下面的代码: <package name ="upload" extends="struts-default" namespace =

  •   VIm学习笔记

    VIm学习笔记 VIM(interface improvrd VI)是VI(visual interface)的增强版,是处理ASCII码的模式化的文本编辑器,功能很多,对于我们初学者来说,只需要先学会基本的操作就可以了,好了废话不多说,直接进入主题. VI的三种模式:命令行模式(command mode),为刚进入VI的默认模式,此在此模式中,向里面输入的任何数据VI都会把它理解为命令----表现为扬声器在不停的滴滴作响,也就是说在命令行模式是不能输入任何数据的,只能输入命令. 想要对文件进行

  • J2EE学习笔记

    J2EE学习笔记 By huihoo.com顾志凌(rockygu@citiz.net) 灰狐动力--致力于中间件技术的研究.应用与开发 http://www.huihoo.com 注:框架可以用Word菜单中的 "视图/文档结构图" 看到 J2EE模式 Value Object(值对象) 用于把数据从某个对象/层传递到其他对象/层的任意Java对象. 通常不包含任何业务方法. 也许设计有公共属性,或者提供可以获取属性值的get方法. JSP 1.JSP的基础知识 __ _____ |

  • sql教程&amp;学习笔记(不断更新)

    学习笔记: 判断在某段时间内 一.select * from table where talbe.time between to_date('2006-1-15','yyyy-mm-dd') and to_date('2008-1-15','yyyy-mm-dd') order by talbe.time; select * from table where talbe.time between trunc(date(formDate) )and trunc(date(toDate) )orde

Tags: