POJ3614 Sunscreen 贪心入门
2024-10-01 07:05:30
题目大意
给出一些区间和一些点,一个点如果在一个区间内,那么此两者可以匹配。问匹配数最大是多少。
题解
这样的题我们一般都是站在区间上去找与其配对的点。我们可以得到如下性质:
对于一段区间\([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;
}
最新文章
- jq添加数组
- ASP.NET MVC5 网站开发实践(二) Member区域&ndash;管理列表、回复及删除
- PPTP部署文档
- Repeater删改
- 完美解决IE6不支持position:fixed的bug
- Flash制作遇到的小问题1--为何变形需要将图形打散(Ctrl+b)
- python(3)-集合
- keil优化等级设置
- 怎样用jQuery自带方法/函数来获取outerHTML属性
- hdu2712(贪心)
- 堆C数组实现
- jg-table 过程2 ( jgTable )
- C语言之总结3
- Excel的 OleDb 连接串的格式(Provider=Microsoft.ACE.OLEDB)
- Cocos2dx 学习笔记整理----场景切换
- Hibernate-day02
- SpringDataJPA
- jquery九大选择器的用法举例
- 16个PHP设计模式详解
- Java,数据库中的数据导入到Excel
热门文章
- C#利用ICSharpCode将远程文件打包并下载
- 快速录入快递地址API接口实现
- bootstrap表格样式
- openMSP430之openmsp430-loader
- 安装pywinauto的步骤
- node phantomjs linux 安装问题
- Jenkins构建项目
- MySQL+Keepalived实现主主高可用方案
- BZOJ 3012: [Usaco2012 Dec]First! 字典树 + tarjan
- Docker 导入镜像报错:open /var/lib/docker/tmp/docker-import-743441288/redis-3.0.7/json: no such file or directory