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 Snow_storm at 2011-03-29 02:31:46 on Problem 1505 and last updated at 2011-03-29 02:37:18
贪心:题目要求划分的区间编号字典序最小,因此需要从右向左贪心,若当前区间和>二分枚举值maxs 则区间数+1

判断可行性时,
1.if book[i]>maxs return false
2.只要是需要的区间个数<=m 即return true

二分结束后,
1.再执行一次judge过程,以便pos数组保存的是最终的结果
2.从小到大,将区间个数补足m个

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