poj2008【优先队列】哞大学之校队选拔._第1页
poj2008【优先队列】哞大学之校队选拔._第2页
poj2008【优先队列】哞大学之校队选拔._第3页
poj2008【优先队列】哞大学之校队选拔._第4页
poj2008【优先队列】哞大学之校队选拔._第5页
已阅读5页，还剩10页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、哞大学之校队选拔（POJ2008） Starry 2021-7-11 1 Problem 今年，有N(=1000)头小牛竞争加入校体操队。 每头牛的身高为H，重量为W(0H,W100000)。 要求从这些牛中选最多的牛组成集合，并且集合 要满足下列条件： A*(H-h) + B*(W-w) = C h,w指的是这选择的牛中的H的最小值、W的最小 值。 计算出最大队伍中牛的数量。 2 Analysis从上面的公式可以看出，其实A，B是常数我们可以直接 乘到原来H，W里面 公式就变成了(H-h)+(W-w)=C (H+W)-(h+w)=h，wi=w， A*(hi-h) + B*(wi-w) = C

2、。 根据线性规划知识 hi h=C/A h=0 = w=C/B 这些点都在一个直角三角形内，两条直角边长度 为cw=C/A,ch=C/B。 。 h w (w,h) C/A C/B 2 Analysis 于是 我们的问题转化为用这样一个三角形最多能框住 多少点，且根据题意w,h为点集坐标最小值，即三 角形两条直角边上都要有点。 2 Analysis 求出经过一个点的所有可能存在的三角形。 其实也就是在该点下方的灰色区域中选择点来确 定一个三角形。 2 Analysis 求出经过一个点的所有可能存在的三角形中，最 多包含的点数。 求一个三角形内的点数，可以分解为一个矩形内 的点数减去一个梯形内的点

3、数。 2 Analysis 用这个方法，求出最上面那个三角形的点数之后。 可以继续递推得到下面其他三角形的点数。 2 Analysis 如果点按照高度排序以后，那么后面矩形里的点 一定是后出现的。这样就可以做到随时增加矩形。 2 Analysis 但是减去梯形这个操作，就难理解一点，把点按 照A*H + B*W来排序，就能保证后面梯形里的点 一定是后出现的。 直线:A*(H-h) + B*（W-w）-C = 0。 根据点到直线的距离公式： d=|A*(H-h)+B*(W-w)+C|/A2+B2 把点按照A*H + B*W来排序，就能保证后面梯形 里的点一定是后出现的。 h w (w,h) C/A C/B 2 Analysis 那我们就可以首先求出第一个三角形的点数，然 后接下来的三角形就根据减去梯形，和增加矩形 的操作，来做小的调整就可以了。 在代码里面的表现形式就是维护两个指针，不断 向后移，中间剔除横坐标不

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论