合金

标志: metal.*

试题描述:

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。

现在,用户给出了 n 种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且是用这些原材料可以加工出用户需要的所有种类的合金。

 

输入文件的第一行是两个整数 m n (m, n <= 500) ,分别表示原材料种数和用户需要的合金种数。

2 m+1 行,每行三个实数 a, b, c, (a, b, c >= 0 a+b+c = 1) ,分别表示铁铝锡在一种原材料中所占的比重。

m+2 m+n+1 行,每行三个实数 a, b, c, (a, b, c >= 0 a+b+c = 1) ,分别表示铁铝锡在一种用户需要的合金中所占的比重。

输出一个整数,表示最少需要的原材料种数。若无解,则输出 -1

输入样例:

3 2

0.25 0.25 0.5

0 0.5 0.5

1 0 0

0.7 0.1 0.2

0.85 0.05 0.1

 

输出样例:

2




   这道题是一个很难的问题。

   首先不难看出,合金的三种成分中只有两种成分的数据是有用的,因为第 3 种成分的比例可以由前两种成分的比例推出。因此,对于每一种合金,都可以用唯一的有序实数对 (x, y) 来进行表示。

  那么,给出的若干合金可以表示成为二维平面上的若干点,那么,这些合金可以合成的合金的范围应该是什么呢?

  试考虑将任意两种合金 (x1, y1), (x2, y2) 等比例进行混合,则新合金在平面上的坐标应该表示为:((x1+x2)/2,(y1+y2)/2) ,也就是这两点连线上的中点。

  换句话说,如果平面内任意两个给定的点所代表的合金都可以得到,则这两点连线的中点所代表的合金也可以得到。熟悉凸包的选手一下子就可以想到,敢于凸包凸性的定义中最为简洁的一条是:对于任意(x1,y1),(x2,y2)属于D有 ((x1+x2)/2,(y1+y2)/2)D 。因此,用平面上若干点所代表的合金,能且仅能合成这若干点构成的凸包内的所有点所代表的合金。

  由此,本题就变成了如下的题目:设提供的合金点集为 A ,用户定制的合金点集为 B ,从 A 中选取最少的点,使得 B 中所有点都在 A 中选取点的凸包内。(也可以认为,从 A 中选取的所有点必须构成凸多边形)。

  这并不是一个很容易解决的问题。

 

  既然不能一下子解决,我们先来看几种特殊情况。(设选取的点数为 k

1、 无解。求取 A 点集的凸包,判断 B 中是否所有点都在凸包内。

2、 K=1: 只有一种情况: B 点集内只有一个点(或多个重点),且 A 点集中恰有这个点。

3、 K=2: B 点集所有点共线,且 A 点集中存在两个点,满足这两个点与 B 点集中所有点共线,同时 B 点集中所有点都落在这两个点所连接形成的线段上。

4、 K=3: 这时就没有前两种情况那么简单了。我们考虑使用穷举法解题。当然,如果枚举三角形的三个顶点的话,是超时的,因为验证还需要线形的时间。但实际上,深入思考的话,我们发现只需要枚举三角形的底边就可以了。

设底边为 CD ,则如果以 CD 为底边的三角形满足题意的话,必然有:

(1) B 点集中所有点均位于 CD 边的同侧。

(2) 、如右图。当且仅当在 A 区域中存在 A 点集中的点,此时的三角形覆盖才是可行的。

5 K=4: K=3 时一样处理。此时必然构成一个 四边形。我们枚举四边形的对角线,然后对两侧模仿 k=3 的情形如法炮制。时间复杂度仍然为 O(n3) (较松)

 

以上我们讨论了无解和 k<=4 的所有情况,事实上,如果对于这些情况全都不符合的数据输出 5 的话,则这样的程序可以拿到满分,因为本题的数据的答案都不超过 5 (好弱的数据!!!)但是,本题事实上还有不骗分的算法——甚至比分类讨论的算法时间都要少。

 

试考虑将 A 点集中的所有点看作一个图的顶点,则“选取点”的工作可以看作是图中的一个回路。这个回路应该满足下列性质:

1、 B 点集中所有点必须在回路中任意一条边的同侧。

2、 B 点集中任意一点 (xx, yy) ,则回路中所有边对该点形成的圆心角的度数之和应该为 2pi. (或者说,至少为 2pi ,因为绕圈也是允许的)。(如右图)

3、 回路上的顶点数应尽可能的少。

根据这几条性质,我们可以构造一个图 G

1、 如果 B 点集中所有点并不在某条边的同侧,则删去这条边。

2、 否则,边权等于这条边所对应的圆心角的角度。注意:角度是有符号的,且 v(k1, k2) = -v(k2, k1) ,而角度的符号可以这样定义:如果中心点 O 在向量 v(k1, k2) 的右手螺旋方向,则向量 v(k1, k2) 所成的圆心角是正的,否则是负的。

 

  然后我们考虑算法。注意到这并不是一个经典的最短路径问题,而是一个在权值和不小于给定值的条件下求最少顶点的路径。由于本题中构作图的特殊性质,可以用一种迭代的方法进行:每次枚举一步,然后判断这一步之后各点的权值和情况,取最大值即可。由于本题中图的特殊性,所以这样得出来的解肯定是满足题意的。

  用这种算法作为主题,再加上前面讨论过的 k=1, k=2 和无解这三种特殊情况的判断,就可以完美的解决问题了。(当然,无解情形可以用迭代 n+1 次但还未找到解的情况代替,但这样做很慢,而且无法通过给定的数据)


posted on 2009-03-13 13:39 250 阅读(380) 评论(5)  编辑 收藏 引用

FeedBack:
# re: 合金 试题与解答
2009-04-08 22:28 | Cutedog
可否发一下文字版的报告给我,我的Email是zjuer@qq.com
谢谢!  回复  更多评论
  
# re: 合金 试题与解答
2009-04-09 08:14 | 250
对不起 我重做机器是把他搞丢了 你可以上OIBH搜贴 看看能不能找到  回复  更多评论
  
# re: 合金 试题与解答
2009-04-13 16:42 | richardxx
呵呵,分析得相当好哈。
记得你那句"用平面上若干点所代表的合金,能且仅能合成这若干点构成的凸包内的所有点所代表的合金",我当时看黑书时证明了很久~~
  回复  更多评论
  
# re: 合金 试题与解答
2009-04-13 16:45 | 250
能现身么?
QQ|MSN|Gtalk  回复  更多评论
  
# re: 合金 试题与解答
2009-04-14 14:47 | richardxx
@250

我QQ: 22333141
认证写你名字就好,:>
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

留言簿(6)

随笔分类

随笔档案

文章档案

相册

搜索

  •  

最新评论