POJ3614 Sunscreen 贪心入门

题目大意

给出一些区间和一些点，一个点如果在一个区间内，那么此两者可以匹配。问匹配数最大是多少。

题解

这样的题我们一般都是站在区间上去找与其配对的点。我们可以得到如下性质：

对于一段区间\([l_1,r_1]\)的任意两点\(a,b, a<b\)，它们对于任意一个区间\([l_2,r_2],l_2<l_1\)，\(a\in[l_2,r_2]\)的可能性(以后用P表示)\(P(a\in[l_2,r_2])>P(b\in[l_2,r_2])\)。

什么叫“可能性大”呢？暂且规定如果事件A不可能发生的自变量的取值范围比事件B的小，则事件A成立的可能性比B的大。本题中，如果我们让\(a\)位于左区间，那么\(a\notin [l_2,r_2]\Rightarrow a\in(-\infty ,l_2)\cup(r_2,b)\)。而如果我们让\(b\)位于左区间，那么\(b\notin [l_2,r_2]\Rightarrow b\in(-\infty,l_2)\cup(r_2,\infty)\)后者范围比前者大，故性质成立。其它的结论通过类似的方式推导，无法消掉一个无穷，故此方法是对的。

因此，我们可以得到推论：

处理区间集合\(R\)和点集\(A\)时，先将左端点最靠右的区间\(r\)与属于该区间且最靠右的点\(a\)配对，然后子问题\(R-\{r\},A-\{a\}\)所能配对的数量是最多的。

凭什么就要选左端点最靠右的区间？因为先选了它并不会使结果变差。

由此我们就得到了贪心算法：给点按位置从大到小排序，区间按左端点位置从大到小排序，然后按以上黑体字做即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_POINT = 3000, MAX_RANGE = 3000;

struct Point

{

	int Num, P;

}_points[MAX_POINT];

struct Range

{

	int L, R;

}_ranges[MAX_RANGE];

bool CmpPoint(Point& a, Point& b)

{

	return a.P > b.P;

}

bool CmpRange(Range& a, Range& b)

{

	return a.L > b.L;

}

int main()

{

	int totRange, totPoint;

	scanf("%d%d", &totRange, &totPoint);

	for (int i = 1; i <= totRange; i++)

		scanf("%d%d", &_ranges[i].L, &_ranges[i].R);

	for (int i = 1; i <= totPoint; i++)

		scanf("%d%d", &_points[i].P, &_points[i].Num);

	sort(_ranges + 1, _ranges + totRange + 1, CmpRange);

	sort(_points + 1, _points + totPoint + 1, CmpPoint);

	int ans = 0;

	for (int i = 1; i <= totRange; i++)

	{

		for (int j = 1; j <= totPoint; j++)

		{

			if (_points[j].Num > 0 && _ranges[i].L <= _points[j].P && _points[j].P <= _ranges[i].R)

			{

				ans++;

				_points[j].Num--;

				break;

			}

		}

	}

	printf("%d\n", ans);

	return 0;

}