Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

非降排序+贪心

Posted by jinyingqi at 2011-04-14 12:50:52 on Problem 1065
题意: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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator