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