贪心 黑白点对问题_设平面上分布着n个白点和n个黑点,每个点用一对坐标(x, y)表示。一个黑点b=(xb,yb)

题目描述

设平面上分布着n个白点和n个黑点，每个点用一对坐标（x, y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。

Input
输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n<16)；第二行含2n个实数xb1, yb1,xb2, yb2,…, xbn, ybn， (xbi, ybi)，i=1, 2, …, n表示n个黑点的坐标；第三行含2n个实数xw1, yw1,xw2, yw2,…, xwn, ywn，(xwi, ywi)，i=1, 2, …, n表示n个白点的坐标。同一行的实数之间用一个空格隔开。

Output
对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。

贪心策略分析

首先定义一个概念：配对指数。配对指数是指某个点能匹配的个数。无论黑白点，配对指数最小的优先获得匹配权（配对指数为0除外）。

eg: 假如某个黑点的配对指数为a(a>0)，是所有黑白点中最小的，那么它优先配对，接着在这个黑点能配对的a个白点中选出最小配对指数的白点。

此贪心策略能否达到全局最优？我不知道怎么证明声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/716486