white_black
所属分类：数据结构
开发工具：Visual C++
文件大小：367KB
下载次数：20
上传日期：2011-03-11 13:26:10
上 传 者：
zaclina
说明： 1、问题描述
设平面上分布着n个白点和n个黑点,每个点用一对坐标(x, y)表示.一个黑点b=(xb,yb)支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw.若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对).在一个黑点最多只能与一个白点匹配,一个白点最多只能与一个黑点匹配的前提下,求n个白点和n个黑点的最大匹配对数.
2、具体要求
要求:时间效率在O(NlgN)
3、实现方法
基于贪心算法
以x坐标的升序对黑点排序(可用QUICKSORT或者HEAPSORT),对白点生成一个小根堆!
(1 Description of the problem based on the distribution of plane n-n-white spots and black spots, each point with a pair of coordinates (x, y) said. A black point b = (xb, yb) dominating a white point w = ( xw, yw) if and only if xb> = xw and yb> = yw. If the black point b dominant white w, then the black point and white point w b can match (which can form a matched pair). in a black spot at most can only be matched with a white spot, a white point can only match with the premise of a black point, find the n-n-white spots and black spots on the maximum number of matches. 2, specific requirements requirements: time efficiency in the O ( NlgN) 3, Implementation of the greedy algorithm based on x coordinates in ascending order of black spots (available QUICKSORT or HEAPSORT), generating a small white spot root heap!)
文件列表:
2008301500209：黑白点问题\1.cpp (3079, 2010-12-31)
2008301500209：黑白点问题\1.dsp (3341, 2010-12-31)
2008301500209：黑白点问题\1.dsw (510, 2010-12-31)
2008301500209：黑白点问题\1.ncb (41984, 2010-12-31)
2008301500209：黑白点问题\1.opt (48640, 2010-12-31)
2008301500209：黑白点问题\1.plg (723, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.cpp (3079, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.dsp (3341, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.dsw (510, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.ncb (41984, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.opt (48640, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\1.plg (723, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\1.exe (184371, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\1.ilk (182908, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\1.obj (6480, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\1.pch (225956, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\1.pdb (451584, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\vc60.idb (33792, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug\vc60.pdb (45056, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\resource.h (411, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Script1.rc (1447, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Script2.rc (2552, 2010-12-31)
2008301500209：黑白点问题\Debug\1.exe (184371, 2010-12-31)
2008301500209：黑白点问题\Debug\1.ilk (182908, 2010-12-31)
2008301500209：黑白点问题\Debug\1.obj (6480, 2010-12-31)
2008301500209：黑白点问题\Debug\1.pch (225956, 2010-12-31)
2008301500209：黑白点问题\Debug\1.pdb (451584, 2010-12-31)
2008301500209：黑白点问题\Debug\vc60.idb (33792, 2010-12-31)
2008301500209：黑白点问题\Debug\vc60.pdb (45056, 2010-12-31)
2008301500209：黑白点问题\resource.h (411, 2010-12-31)
2008301500209：黑白点问题\Script1.rc (1447, 2010-12-31)
2008301500209：黑白点问题\Script2.rc (2552, 2010-12-31)
2008301500209：黑白点问题\2008301500209：黑白点问题\Debug (0, 2011-01-11)
2008301500209：黑白点问题\2008301500209：黑白点问题 (0, 2011-01-11)
2008301500209：黑白点问题\Debug (0, 2010-12-31)
2008301500209：黑白点问题 (0, 2011-01-11)
近期下载者：
相关文件：
收藏者：