随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

POJ 1990 MooFest 数状数组

题目大意:
  有N头牛,站在X轴上,没有共点的情况,每个牛有一个听力值V(i),他们交流所消耗的最少volume为abs(X(i)-(X(j)))*MAX{V(i),V(j)}
         最后再求总和。
由于数据量最大为20000,显然O(n^2)的算法会超时。先按V值进行从小到大排序可解决MAX的问题,最后就是对每头牛求V值小于他的权值了。
对于第i个牛,在0~i-1中,用两个数状数组,a表示坐标小于x[i]的个数,b表示坐标小于x[i]的牛的坐标之和,另外c表示0~i-1中所有牛的坐标之和。

posted on 2010-05-06 17:20 acleast 阅读(233) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理