Rocket Fuel Online Test原题！

回馈大家 ONLINE TEST 3小时， 做一个auto racer的题：

Input:
Id, startTime ,EndTime

Output:
Id, score

大意是让你设计一个算法来评价每个赛车手的成绩， 根据[size=14.3999996185303px]startTime[size=14.3999996185303px] 和[size=14.3999996185303px]EndTime。 算法里面有具体要求：
[size=14.3999996185303px]判断快的条件：A.startTime>B.startTime && [size=1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

ore就是比该车手要快的人的个数


我用的是二叉树， 但最后2个test cases还是timeout了

请问有做过的同学出来吼一声啊。。
说说你们有拿到ONSITE吗？
谢谢了

就是问你一个区间能被多少个区间完整覆盖吧。。。。可不可以这样离线做，把线段按左端点排序，然后对于一个线段[l,r]，之前的线段左端点都是小于l的，去query比它的右端点r大的有多少，就是query [r+1, +oo]这个区间有多少个数，最后把它的右端点r的个数＋1，这些query和update可以logn时间完成

1guangnian 发表于 2014-11-1 04:40
就是问你一个区间能被多少个区间完整覆盖吧。。。。可不可以这样离线做，把线段按左端点排序，然后对于一个 ...

恩。基本没问题。

题目中不是提示用bucket做吗，按照start time分bucket，可以跑过所有test，3小时还是比充裕的。

xx8833 发表于 2014-11-1 07:30
题目中不是提示用bucket做吗，按照start time分bucket，可以跑过所有test，3小时还是比充裕的。

我没太明白用bucket怎么记录结束时间比目前记录要晚的数目

yyboyz 发表于 2014-11-1 07:35
我没太明白用bucket怎么记录结束时间比目前记录要晚的数目

bucket中按照end时间排序，就能二分搜索了。如果bucket大小选为sqrt(n)，复杂度是n * (sqrt(n) + sqrt(n)*log(sort(n)))。对于每个racer，有一个bucket需要枚举（start time正好在那个bucket范围中），其他bucket都是二分。

那你怎么算出结束时间小于某个值的个数?

我今天也做了这个……最后用线段树把大数据量的test case都搞过去了……但最后test case2一直过不去不知道怎么回事

没过最后两个大case正常的，因为95%时间都在I/O上，不是程序问题