算法复杂度:O(m+n)(假定girl和enemy都有序,实际题目,不记得,如果不是有序,那么先排序,采用计数排序的话,如果范围不大还可以进一步减小算法复杂度)
O(MlogM+nlogN)
实际过程是:采用归并排序过程中合并计算移动平均数
public class SpaceWarDiv1 { /** * 实际上是求移动平均数(实际计算只需要2个变量,而不是sum变量个数) * a<sub>i</sub>表示第i个girl,b<sub>j</sub>表示第i个enemy * 用sum[i]表示倒数第i个girl能打死的enemy总数sum[0]表示最强girl可以打死的人数 * 实际求的是max{sum[0],sum[0:1]/2,sum[0:3]/3..... * @param magicalGirlStrength * @param enemyStrength * @param enemyCount * @return */ public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) { int i=magicalGirlStrength.length-1; int j = enemyStrength.length-1; if(enemyStrength[j]>magicalGirlStrength[i]) return -1L; long sum[]=new long[2]; sum[0]=0; sum[1]=0; long maxVal = 0; int count=0; while(i>=0&&j>=0) { while(i>=0 && magicalGirlStrength[i]>=enemyStrength[j]) i--; if(i<0) break; while(j>=0&&magicalGirlStrength[i]<enemyStrength[j]) { sum[1] += enemyCount[j]; j--; } //girl >=enemy;calc last gir sum //sum[i+1] { //average count = magicalGirlStrength.length-i-1; long average = (sum[1]+sum[0]+count-1)/(count); maxVal = (maxVal>average)?maxVal:average; } sum[0] = sum[0]+sum[1]; sum[1]=0; } while(j>=0){ sum[1] += enemyCount[j]; j--; } { //average count = magicalGirlStrength.length-i-1; long average = (sum[1]+sum[0]+count-1)/count; maxVal = (maxVal>average)?maxVal:average; } return maxVal; } public static void main(String args[]) { int []magicalGirlStrength=new int[]{2,3,5}; int[] enemyStrength = new int[]{1,3,4}; long[] enemyCount =new long[]{2,9,4}; // int []magicalGirlStrength=new int[]{2,3,5}; // int[] enemyStrength = new int[]{1,1,2}; // long[] enemyCount =new long[]{2,9,4}; System.out.println(new SpaceWarDiv1().minimalFatigue(magicalGirlStrength, enemyStrength, enemyCount)); } }
相关推荐
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
关于TopCoder的竞赛指导,不仅仅是SRM,还有Bug Race、软件比赛的资料,是我从网上收集的,大部分是中文的
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候,比赛时间与我的工作/其他活动冲突,因此我对TopCoder不太活跃。 但是我尽力去参加比赛,因为这很有趣。 就像在任何在线比赛中所期望的那样,代码...
topcoder-srm 顶级编码器srm问题集锦
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
topcoder竞赛的算法讲座ppt
TopCoder比赛登录使用的客户端,需要配置Java环境
topcoder算法讲座ppt
topcoder arena,包含ContestAppletProd.jnlp,CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
TopCoder新手入门指南,一步步操作既可以了,然后开启您的Topcoder编程之旅吧。
Topcoder的Java客户端,安装前确定已经安装了JRE
用于topcoder的第3方编辑器插件。
TopCoper SmartWordToy problem 解决方法,C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
给新手提供的TopCoder注册方法和平台使用 十分详细
topcoder的比赛作品,编译通过的。可以放心使用。
topcoder入门,对想做tc,但又不知道怎么搞的很有帮助,我首先也不知道搞。
这是一类关于acm学习的资料,它详细的说明了Acm学习的内容,如何提高编写软件的能力
关于TopCoder的一些程序竞赛的相关资料