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

O(n^2)的算法

Posted by piaoyaozijian1 at 2009-03-17 14:31:57 on Problem 2008 and last updated at 2009-03-17 14:34:14
  这题做了几天,WA了几次TLO了几次,参考前辈的算法,才终于AC了,但他们说的不是很清楚,我再写详细一点,因为知道那种做不出来的感觉真是太难受了,仅供借鉴....
 首先,h和w是选出来的Team中最小的H和W,一开始没看懂WA了几次...汗啊...
 如果用三次循环,时间复杂度太高,超时,那时真是一点办法没了,后来看到一个有O(n^2)的算法,看了半天没看懂啊,还好最后看懂一点了(谢前辈啊),现在把伪码写出来,希望大家可以少走弯路了:

   定义struct clves{
       long w;long h;long test;//test=A*w+B*h

       }
 clves cl[number];cll[number]//cl和cll分别按cl[].w和cll[].test从小到大排序

1:i=0;sum1=0
2:minh=cll[i].h;i++;置j=0;k=0;sum2=0;if(i=number)到
 3:minw=cl[j].w;j++,如果j=number回到2;
   4:从k开始在cll中找满足条件的牛,如果 cll[k].test>minh*A+minw*B+C转到5;
     否则 如果(cll[k].h>=minh&&cll[k].w>=minw)sum2++;
   5:sum1=sum1>sum2?sum1:sum2;
   6:判断cl[j]是否是sum2中的牛,如果是sum2--;回到3;
7:得到结果最大组数sum1;

参考资料:
    http://shangjb91.ycool.com/post.1748233.html
   测试数据:http://ace.delos.com/MAR04_5.htm

感谢luzilon给的数据

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