首页 > 代码库 > 【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总结