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 xuchang at 2011-04-13 16:15:17 on Problem 1456 and last updated at 2011-04-13 16:15:42
In Reply To:并查集 Posted by:2008022118 at 2010-02-28 22:54:24
> 小规模数据按时间排序直接贪心;
> 此题,按利润排序,然后用以时间为并查集+贪心;
> 当谈得一个物品后,这个天数的父结点设为该天数减1;
> //init fa[i] = i;
> if ((td = find(product[i].day)) > 0)
> {
>    totalp += product[i].p;
>    fa[td] = td - 1;//即下一个deadline为td的物品只能是td-1天卖了
> }



经过我的测试,在你的if里如果再加上一句fa[product[i].day] = td - 1; 可以使时间再缩短1/3

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