首页 > 代码库 > 【Topcoder】SRM157 DIV2总结
【Topcoder】SRM157 DIV2总结
250分题:简单的二分,就是平常玩的猜数字游戏
代码:GitHub
500分题:给出一个员工一天的打卡时间段,要求求出员工这一天的工资。其中正常上班时间是6:00:00到18:00:00,薪水是wage,其他时间薪水是1.5*wage。
我的思路比较直接,将时间分成三个时间段分别计算:00:00~06:00,06:00~18:00,18:00~23:59:59。伪码如下:
1 if(arrival time < 06:00:00) 2 money += 1.5*wage*(min(06:00:00,departure time)-arrival time); 3 if(departure time > 06:00:00) 4 arrival time = 06:00:00; 5 6 if(arrival time >= 06:00:00 && arrival time <18:00:00) 7 money += wage*(min(departure time,18:00:00) - 06:00:00); 8 if(departure time > 18:00:00) 9 arrival time = 18:00:00;10 11 if(arrival time >= 18:00:00)12 money += 1.5*wage*(departure time - arrival time);
具体实现的时候,我直接用了java的date类,算时间差的时候就很麻烦,其实只要把所有时间都转换成秒,然后计算这个人每秒赚多少钱,这样无论是比较时间的大小还是计算两个时间点的差值都非常容易。所以积累一点,以后遇到要比较时间大小和差值的,尽量转换成秒来计算,会省去很多麻烦。不过今天做了半天,积累了一些关于java的date类的知识,积累如下:
1.讲形如“HH:mm:ss”的字符串转换为Date型:
SimpleDateFormat fommater = new SimpleDateFormat("HH:mm:ss");Date arriDate = fommater.parse(arrival);
上述的parse函数可能会抛出ParseException异常,需要处理。
2.判断时间t1是否在时间t2的前面或者后面:
t1.before(t2);t1.after(t2);
3.求时刻t1和t2的差值(单位是毫秒)
long bewteen = t1.getTime() - t2.getTime();
最后完整的代码:GitHub
这道题官方还给了一个很简便的解法:把arrival time和departure time都变成秒为单位后,直接从arrival time一秒一秒的遍历到departure time,如果当前的一秒在正常上班范围内,增加计数器t1;如果在加班的范围内,增加计数器t2,最后得到的钱就是wage*t1+1.5*wage*t2(wage是每秒赚的钱)。这个方法比上面分三段判断实现起来要简单很多。
1000分题:给出两个沙漏,一个可以用来衡量出时间glass1,一个可以用来衡量出glass2,要求求出前十个最小的能够衡量出的时间。
第一眼看没思路,看了解答才发现要用递归+备忘录的方法:递归函数helper定义为void helper(int sand1,int sand2,int time)表示在时刻time,两个沙漏分别能够衡量出时间sand1和sand2,此时有两种可能
1.sand1或者sand2至少一个漏空了,那么我们有四种选择:
(1)把sand1倒过来,sand2不动,递归调用helper(glass1-sand1,sand2,time);
(2)把sand2倒过来,sand1不动,递归调用helper(sand1,glass2-sand2,time);
(3)把sand1和sand2全部倒过来,递归调用helper(glass1-sand1,glass2-sand2,time);
(4)sand1和sand2都不动,等待没空的那个漏空,此时需要看两个沙漏哪个还没漏完,假设1还没漏完,就递归调用helper(0,0,time+sand1);
2.sand1和sand2都没有漏空,那么我们必须要等待他们中有较少的沙的沙漏漏完才能有动作,此时递归调用helper(sand1-min(sand1,sand2),sand2-min(sand1,sand2),time+min(sand1,sand2)。
如果单纯的递归会超时,因为对于同一组(sand1,sand2,time),在递归的过程中,我们可能会多次重复调用,所以要用备忘录visited[][][]记录我们掉用过哪些sand1,sand2,time,避免重复的调用。
最后代码:GitHub
官方完整题解
【Topcoder】SRM157 DIV2总结