| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
非降排序+贪心题意:t组测试数据,每组n块木头,每块木头有相应的length和weight。现在对n块木头进行处理,setup time如下定义:
1、处理第一块木头setup time为1
2、如果后来处理木头的length和weight分别都不小于前一块的length和weight,则不需要setup time,否则setup time加一
求处理全部木头的最小setup.
分析:
1、首先对木头进行非降排序,每个木头的结构为(l,w),以length为主元素,weight为次元素。
(l1,w1)>(l2,w2)的条件是l1>l2 || (l1==l2 && w1>l2)
2、其次进行贪心选择。初始计数器c=0, 每次从排序好的木头前面选择未使用过的木头(l,w)做为当前木头,然后标记已用,遍历之后没有用过的木头(l1,w1),如果有(l1>=l&&w1>=w)则置(l1,w1)为已用并且替换当前木头为(l1,w1)。每次遍历之后计数器c加1,如果c等于总木头数退出,否则跳到步骤2.
解题报告
http://blog.csdn.net/koala002/archive/2011/04/14/6322826.aspx
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator