关于邮寄485的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

关于邮寄485的问题

关于邮寄485的问题# EB23 - 劳工卡

c*m2015-07-24 07:07

1 楼

一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度o(nlgn).
这题什么思路呢？interval tree? nlgn的想法想不到啊。

s*02015-07-24 07:07

2 楼

自己是2月初递的485，现在还没批。可看板上都批到三月中了。现在自己很不淡定。。
。。
不知道版上还有没有2月份没批的？谢谢！

l*i2015-07-24 07:07

3 楼

和ld异地，但都是交在NSC，这种情况提交485时能放一个信封交吗？
打指纹是不是会被各自安排居住附近的地点？

y*k2015-07-24 07:07

4 楼

排序加点数学。

b*e2015-07-24 07:07

5 楼

TSC吗？如果是NSC, 要有坏的心理准备。

【在 s**********0 的大作中提到】

: 自己是2月初递的485，现在还没批。可看板上都批到三月中了。现在自己很不淡定。。
: 。。
: 不知道版上还有没有2月份没批的？谢谢！

r*e2015-07-24 07:07

6 楼

到达时间放进order-statistic tree
然后根据出发从早到晚，依次查询到达时间的rank，也就是score
同时每查询一个，就从tree里删掉一个
每次查询和删除都是O(lgn)

间

【在 c*********m 的大作中提到】

: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。

m*i2015-07-24 07:07

7 楼

呵呵。小概率事件吧

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 s**********0 的大作中提到】

: 自己是2月初递的485，现在还没批。可看板上都批到三月中了。现在自己很不淡定。。
: 。。
: 不知道版上还有没有2月份没批的？谢谢！

f*e2015-07-24 07:07

8 楼

这题我发过，n1=|arrival < this arival|
n2=|start < this start|
n1 - n2

【在 y**k 的大作中提到】

: 排序加点数学。

s*02015-07-24 07:07

9 楼

TSC

c*m2015-07-24 07:07

10 楼

你能说得详细点吗？不太明白，谢谢。

【在 f*****e 的大作中提到】

: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2

b*e2015-07-24 07:07

11 楼

有希望本周绿

【在 s**********0 的大作中提到】

: TSC

c*s2015-07-24 07:07

12 楼

汗他们 online test..是线段树

z*y2015-07-24 07:07

13 楼

还有去年11,12的没批的么

B*t2015-07-24 07:07

14 楼

这不是类似merge interval么？难道我理解错题意了？
BTW: 我申他家上来就让我写个tail命令的实现

s*02015-07-24 07:07

15 楼

谢谢大蜜蜂！Hope it comes true.

【在 b*******e 的大作中提到】

: 有希望本周绿

s*r2015-07-24 07:07

16 楼

这个思路好不用什么线段树了

【在 f*****e 的大作中提到】

: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2

m*i2015-07-24 07:07

17 楼

RFE过吗？前续动作都完成了？

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 s**********0 的大作中提到】

: TSC

c*m2015-07-24 07:07

18 楼

你能详细说下嘛？没太明白这个思路啥意思，真写代码肯定没法用线段树啦啊，谢谢!

【在 s*******r 的大作中提到】

: 这个思路好不用什么线段树了

s*02015-07-24 07:07

19 楼

没有ref过。2月8号递的485。3月2号收到打指纹通知。3月20号收到的AP和LCD。3月24
号打的指纹。然后就没动静了=（

m*82015-07-24 07:07

20 楼

可是n2里的racer不见得都在n1里吧，也有出发早但到的晚的啊

【在 f*****e 的大作中提到】

: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2

b*e2015-07-24 07:07

21 楼

not REF, but RFE.
虽然我一直不知道REF 这个词怎么来的。

24

【在 s**********0 的大作中提到】

: 没有ref过。2月8号递的485。3月2号收到打指纹通知。3月20号收到的AP和LCD。3月24
: 号打的指纹。然后就没动静了=（

t*32015-07-24 07:07

22 楼

什么是rf？

s*02015-07-24 07:07

23 楼

=D....

w*y2015-07-24 07:07

24 楼

rocket fuel?

【在 t*******3 的大作中提到】

: 什么是rf？

b*e2015-07-24 07:07

25 楼

EB1的同学自我要求要高点，hiahia

【在 s**********0 的大作中提到】

: =D....

b*n2015-07-24 07:07

26 楼

My C++ implementation:
#include
#include
#include
using namespace std;
// intervals: each racer's starting and ending times,
// returns a vector of scores for all racers.
vector get_scores(const vector >& intervals) {
size_t len = intervals.size();
vector scores(len, 0);
// Sort starting and ending times by putting them into two maps.
// Time complexity: (n*logn)
map starts; // key: starting time, value: original index
map ends; // key: ending time, value: original index
for (size_t i = 0; i < len; i++) {
starts[intervals[i].first] = i;
ends[intervals[i].second] = i;
}
// Start from the racer who starts the first,
// find how many racers finish earlier than he does.
// Each iteration takes O(logn), so total cost is O(n*logn).
while (starts.size()) {
size_t idx = starts.begin()->second;
int curr_end = intervals[idx].second;
map::iterator it = ends.find(curr_end); // O(logn)
scores[idx] = distance(ends.begin(), it);
// The current racer will never be counted in any other racer's
// scores, so we delete his records from both starts and ends.
starts.erase(starts.begin()); // O(logn)
ends.erase(curr_end); // O(logn)
}
return scores;
}
// Test harness
int main() {
vector > intervals;
intervals.push_back(pair(3, 6));
intervals.push_back(pair(2, 4));
intervals.push_back(pair(0, 8));
vector scores = get_scores(intervals);
for (size_t i = 0; i < scores.size(); i++) {
cout << i << ": " << scores[i] << endl;
}
return 0;
}

间

【在 c*********m 的大作中提到】

s*02015-07-24 07:07

27 楼

hiahia....=)

k*22015-07-24 07:07

28 楼

我code test也是tail命令，不过我第一轮phone interview已经挂了。他家的题目不简
单，大家加油！

K*N2015-07-24 07:07

29 楼

bless

f*e2015-07-24 07:07

30 楼

mark

间

【在 c*********m 的大作中提到】

s*02015-07-24 07:07

31 楼

Thanks. Hope we all can pass GC process ASAP.

h*02015-07-24 07:07

32 楼

--- score ＝所有出发比自己晚但是到达比自己早的racer数量之和, ---
是那些racer的个数, 不是他们的score 之和, 对不?
my idea is:
1 create a map and listA that makes the start
time ordered ,
2 travel the startTime, from big to small, and create a listB to store the
endTime in order
2.1 to the first Race whose startTime is biggest, insert his endTime in
the listB, the position is 0, so the score is 0
2.2 to every Racer, binary search his endTime in listB, the position is
his score.
code:
public boolean calScore(ArrayList racers){
//pre-check
if(racers == null || racers.size() == 0)
return false;

HashMap map = new HashMap();
List startTimeList = new ArrayList();
for(Racer racer : racers){
map.put(racer.getStartTime(), racer);
startTimeList.add(racer.getStartTime());
}
Collections.sort(startTimeList);
List endTimeList = new ArrayList();
Racer racer;
for(int i=startTimeList.size() - 1; i>= 0; i--){
racer = map.get(startTimeList.get(i));
racer.setScore(getPosition(endTimeList, racer.getEndTime()));
}

return true;
}

private int getPosition(List endTimes, int x){
if(endTimes == null || endTimes.size() == 0 ){
endTimes.add(0, x);
return 0;
}

int lower = 0, higher = endTimes.size() - 1, middle;

while(lower <= higher){
middle = lower + ((higher - lower) >> 1);

if(x <= endTimes.get(middle) )
higher = middle -1;
else
lower = middle + 1;

}

endTimes.add(lower, x);
return lower;
}

【在 f*****e 的大作中提到】

: mark
:
: 间

m*i2015-07-24 07:07

33 楼

正常程序之内了
可以偷着乐了：）

24
★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 s**********0 的大作中提到】

: 没有ref过。2月8号递的485。3月2号收到打指纹通知。3月20号收到的AP和LCD。3月24
: 号打的指纹。然后就没动静了=（

x*02015-07-24 07:07

34 楼

mark

s*42015-07-24 07:07

35 楼

Same here. RD 2/2, no status yet...

c*m2015-07-24 07:07

36 楼

你这个代码不是nlgn啦，因为distance函数是O(n)时间的，map的iterator类型不是
Random Access Iterator的，思路是很清晰啦

【在 b*****n 的大作中提到】

: My C++ implementation:
: #include
: #include
: #include
: using namespace std;
: // intervals: each racer's starting and ending times,
: // returns a vector of scores for all racers.
: vector get_scores(const vector >& intervals) {
: size_t len = intervals.size();
: vector scores(len, 0);

b*e2015-07-24 07:07

37 楼

1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
log(n)).
2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
(n)) by sorting e_i.
3. Now traverse (s_i, e_i) from 0 to n:
sorted = [];
for (i = 0; i < n; i++) {
insert_position = binary_insert e_i into sorted;
a_i = c_i - insert_position;
}
This step takes O(n*log(n)) as well.
The result is recorded in a_i.

间

【在 c*********m 的大作中提到】

b*n2015-07-24 07:07

38 楼

请教一下insert to list 怎样才能O(1)?

f*m2015-07-24 07:07

39 楼

"binary_insert e_i into sorted"是在第一步sorted的Interval中insert吗？
好像不对啊。

log

【在 b***e 的大作中提到】

: 1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
: log(n)).
: 2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
: (n)) by sorting e_i.
: 3. Now traverse (s_i, e_i) from 0 to n:
: sorted = [];
: for (i = 0; i < n; i++) {
: insert_position = binary_insert e_i into sorted;
: a_i = c_i - insert_position;
: }

b*e2015-07-24 07:07

40 楼

No. In Step 3, note that I initiated "sorted" as an empty array.

【在 f*********m 的大作中提到】

: "binary_insert e_i into sorted"是在第一步sorted的Interval中insert吗？
: 好像不对啊。
:
: log

s*e2015-07-24 07:07

41 楼

请问这个sorted是按什么sort的？

【在 b***e 的大作中提到】

: No. In Step 3, note that I initiated "sorted" as an empty array.

h*g2015-07-24 07:07

42 楼

间
rf是什么公司？

【在 c*********m 的大作中提到】

f*m2015-07-24 07:07

43 楼

你是说把e_i一个一个放到空的sorted array，然后看每个e_i在sorted array中的位置？
那么什么时候用到s_i的信息呢？
谢谢。

【在 b***e 的大作中提到】

: No. In Step 3, note that I initiated "sorted" as an empty array.

b*e2015-07-24 07:07

44 楼

That was used in the first step...

置？

【在 f*********m 的大作中提到】

: 你是说把e_i一个一个放到空的sorted array，然后看每个e_i在sorted array中的位置？
: 那么什么时候用到s_i的信息呢？
: 谢谢。

p*22015-07-24 07:07

45 楼

tail命令是傻题呀？

【在 k*******2 的大作中提到】

: 我code test也是tail命令，不过我第一轮phone interview已经挂了。他家的题目不简
: 单，大家加油！

r*e2015-07-24 07:07

46 楼

实现unix command "tail"

不简

【在 p*****2 的大作中提到】

:
: tail命令是傻题呀？

p*22015-07-24 07:07

47 楼

实现到啥程度呀？

【在 r*******e 的大作中提到】

: 实现unix command "tail"
:
: 不简

f*m2015-07-24 07:07

48 楼

哦，了解了。
最后一步把e_i插入sorted array,指的是把在第一步中根据s_i排好的e_i按顺序插入到
sorted array，插入一个就看其插入的位置，而不是等到都插入完了再看每个e_i的位
置，对吧？

【在 b***e 的大作中提到】

: That was used in the first step...
:
: 置？

h*02015-07-24 07:07

49 楼

correction:
The operation in listB is not O(logn). We can use a BST to store the endTime
relative position.
class TreeNode{
endTime; //example "201305061323" :) timestamp is better
count; //there are 2 "201305061323", count=2;
leftNodeSum; //the sum of left child's count
TreeNode left;
TreeNode right;
}
int getPosition(TreeNode root, int endTime){
if(endTime == root.endTime)
return root.leftNodeSum;
if(endTime < root.endTime)
return getPosition(root.left, endTime);
else
return root.leftNodeSum + root.count + getPosition(root.right, endTime);
}
note: keeping this BST balanced is not easy coding in interview.

【在 h********0 的大作中提到】

: --- score ＝所有出发比自己晚但是到达比自己早的racer数量之和, ---
: 是那些racer的个数, 不是他们的score 之和, 对不?
: my idea is:
: 1 create a map and listA that makes the start
: time ordered ,
: 2 travel the startTime, from big to small, and create a listB to store the
: endTime in order
: 2.1 to the first Race whose startTime is biggest, insert his endTime in
: the listB, the position is 0, so the score is 0
: 2.2 to every Racer, binary search his endTime in listB, the position is

G*A2015-07-24 07:07

50 楼

我也觉得是merge interval.

【在 B********t 的大作中提到】

: 这不是类似merge interval么？难道我理解错题意了？
: BTW: 我申他家上来就让我写个tail命令的实现

b*e2015-07-24 07:07

51 楼

Yes. That's the trick of this problem.

【在 f*********m 的大作中提到】

: 哦，了解了。
: 最后一步把e_i插入sorted array,指的是把在第一步中根据s_i排好的e_i按顺序插入到
: sorted array，插入一个就看其插入的位置，而不是等到都插入完了再看每个e_i的位
: 置，对吧？

y*k2015-07-24 07:07

52 楼

赞思路清晰。最后一步似需修正。

【在 b***e 的大作中提到】

: Yes. That's the trick of this problem.

b*e2015-07-24 07:07

53 楼

愿闻其详。

【在 y**k 的大作中提到】

: 赞思路清晰。最后一步似需修正。

p*22015-07-24 07:07

54 楼

感觉可以build一个tree，子树的数目就是score

l*g2015-07-24 07:07

55 楼

endTimes.add(lower, x);
----this is an O(n) operation ?

【在 h********0 的大作中提到】

s*n2015-07-24 07:07

56 楼

Insert into BST and get score.
This is runnable code.
class node{
int val;
int below;
node left;
node right;
node(int val){this.val = val; left = right = null; below = 0;}
}
class Tree{
node root;
Tree(){root = null;}
int insert(int val){
node N = root;
if(N == null){
root = new node(val);
return 0;
}
int score = 0;
node par = null;
while(N!=null){
if(val <= N.val){
N.below++;
par = N;
N = N.left;
}else{
N.below++;
if(N.left == null) score++;
else score += 2+N.left.below;
par = N;
N = N.right;
}
}
if(val <= par.val){
node nd = new node(val);
par.left = nd;
return score;
}
else{
node nd = new node(val);
par.right = nd;
return score;
}
}
}

p*22015-07-24 07:07

57 楼

log
sorted = [];
for (i = 0; i < n; i++) {
insert_position = binary_insert e_i into sorted;
a_i = c_i - insert_position;
}
This step takes O(n*log(n)) as well.
这个insert为什么是logn呢？什么数据结构？

【在 b***e 的大作中提到】

p*22015-07-24 07:07

58 楼

怎么没看到start－end？

【在 s******n 的大作中提到】

: Insert into BST and get score.
: This is runnable code.
: class node{
: int val;
: int below;
: node left;
: node right;
: node(int val){this.val = val; left = right = null; below = 0;}
: }
: class Tree{

p*22015-07-24 07:07

59 楼

有现成的order-statistic tree可用吗？感觉也不好写呀。

【在 r*******e 的大作中提到】

: 到达时间放进order-statistic tree
: 然后根据出发从早到晚，依次查询到达时间的rank，也就是score
: 同时每查询一个，就从tree里删掉一个
: 每次查询和删除都是O(lgn)
:
: 间

r*n2015-07-24 07:07

60 楼

这到题难道不是longest increasing subsequence的马甲题吗？

s*n2015-07-24 07:07

61 楼

Complete code:
import java.util.*;
import java.lang.Math.*;
// Customized Tree for sorting ending times and count how many ending times
are earlier than inserted one to compute the racer's score.
// Insertion is O(nlgn)
class node{
int val;
int below;
node left;
node right;
node(int val){this.val = val; left = right = null; below = 0;}
}
class Tree{
node root;
Tree(){root = null;}
int insert(int val){
node N = root;
if(N == null){
root = new node(val);
return 0;
}
int score = 0;
node par = null;
while(N!=null){
if(val <= N.val){
N.below++;
par = N;
N = N.left;
}else{
N.below++;
if(N.left == null) score++;
else score += 2+N.left.below;
par = N;
N = N.right;
}
}
if(val <= par.val){
node nd = new node(val);
par.left = nd;
return score;
}
else{
node nd = new node(val);
par.right = nd;
return score;
}
}
}
// racer class, to store the start and ending time for each racer
class racer{
double start;
double end;
racer(double a, double b){
start = a; end = b;
}
// This function is helper function to create racer, since if start
== end is not allowed.
static racer genRacer(double a, double b){
if(a < b) return new racer(a,b);
else if(a > b) return new racer(b,a);
return null;
}
// Comparison function, used in racer array sorting function
accoring to starting time
static boolean less(racer a, racer b){
return (a.start <= b.start);
}
// Quick Sort for racer class, using comparison function above
static int partition(racer[]a , int left, int right){
int n = a.length;
if(right=n) return -1;
racer p = a[left];
int l = left-1;
int r = right +1;
while(l<=r){
while(++lwhile((--r)>l && less(p, a[r]));
if(l>r) break;
double tmp = a[l].start;
a[l].start = a[r].start;
a[r].start = tmp;
tmp = a[l].end;
a[l].end = a[r].end;
a[r].end = tmp;
}
double tmp = a[left].start;
a[left].start = a[r].start;
a[r].start = tmp;
tmp = a[left].end;
a[left].end = a[r].end;
a[r].end = tmp;
return r;
}
static void subqsort(racer[] a, int left, int right){
int p = partition(a,left, right);
if(p==-1) return;
// System.out.println("Partition at "+p);
subqsort(a,left,p-1);
subqsort(a,p+1,right);
}
public static racer[] sort(racer[] arr){
int N = arr.length;
if(N<=0) return null;
subqsort(arr,0,arr.length-1);
return arr;
}
// Print racer's time virtually
public static void printRace(racer[] arr){
int tt=0;
for(racer i : arr){
System.out.print("#"+(tt++)+":");
int start = (int)(i.start*100);
int end = (int)(i.end*100);
for(int j =0; jSystem.out.print("[");
for(int j =0; jSystem.out.print("]");
System.out.println();
}
}
}
// class to run this algorithm
class run{
// Generate racers with random starting and ending times
static racer[] genRace(int N){
if(N <=0) return null;
racer[] re = new racer[N];
for(int i = 0; iracer R = racer.genRacer(Math.random(), Math.random());
while(R == null) R = racer.genRacer(Math.random(), Math.random()
);
re[i] = R;
System.out.print("( "+ R.start+", "+R.end+" ), ");
}
System.out.println();
return re;
}
// Main function
public static void main(String[] args){
int N = 20;
racer[] race = genRace(N);
race = racer.sort(race);
racer.printRace(race);
Tree T = new Tree();
// Insert into Tree and print out score
for(int i = N-1; i>=0; i--){
System.out.println("#"+i+" score is "+ T.insert((int)(race[i].
end*100)));
}
}
}

【在 p*****2 的大作中提到】

:
: 有现成的order-statistic tree可用吗？感觉也不好写呀。

p*22015-07-24 07:07

62 楼

times
你这个tree是balanced的吗？

【在 s******n 的大作中提到】

: Complete code:
: import java.util.*;
: import java.lang.Math.*;
: // Customized Tree for sorting ending times and count how many ending times
: are earlier than inserted one to compute the racer's score.
: // Insertion is O(nlgn)
: class node{
: int val;
: int below;
: node left;

s*n2015-07-24 07:07

63 楼

OK averg case

【在 p*****2 的大作中提到】

:
: times
: 你这个tree是balanced的吗？

p*22015-07-24 07:07

64 楼

你这个有过他们的test吗？不知道是否能应付一些极端的test case

【在 s******n 的大作中提到】

: OK averg case

s*n2015-07-24 07:07

65 楼

我不知道RF是哪.就是昨天看到这道题，就写了一下。

【在 p*****2 的大作中提到】

:
: 你这个有过他们的test吗？不知道是否能应付一些极端的test case

p*22015-07-24 07:07

66 楼

这个貌似也不对吧？这题感觉不简单呀。尤其是要过OJ。

【在 f*****e 的大作中提到】

: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2

t*q2015-07-24 07:07

67 楼

binary insert为啥是log(n)啊，如何implement？

log

【在 b***e 的大作中提到】

t*q2015-07-24 07:07

68 楼

OJ在什么地方？

【在 p*****2 的大作中提到】

:
: 这个貌似也不对吧？这题感觉不简单呀。尤其是要过OJ。

p*22015-07-24 07:07

69 楼

应该是RF会提供。
这题到现在也没有一个好的说法。算法大家分析的差不多。不过实现不好搞呀。不知道
有没有什么更好的办法。

【在 t*q 的大作中提到】

: OJ在什么地方？

t*q2015-07-24 07:07

70 楼

就是求逆序的加强版啊

【在 p*****2 的大作中提到】

:
: 应该是RF会提供。
: 这题到现在也没有一个好的说法。算法大家分析的差不多。不过实现不好搞呀。不知道
: 有没有什么更好的办法。

p*22015-07-24 07:07

71 楼

什么是求逆序呀？

【在 t*q 的大作中提到】

: 就是求逆序的加强版啊

t*q2015-07-24 07:07

72 楼

http://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9

【在 p*****2 的大作中提到】

:
: 什么是求逆序呀？

p*22015-07-24 07:07

73 楼

哇。太牛了。膜拜一下了。多谢。

【在 t*q 的大作中提到】

: http://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9

i*s2015-07-24 07:07

74 楼

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;
public class Solution {
public static class Racer {
public int start;
public int end;
public int score;
public Racer(int start, int end, int score) {
this.start = start;
this.end = end;
this.score = score;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.
in));
String line;
List racers = new ArrayList();
while((line = in.readLine())!=null){
String[] data = line.split(" ");
racers.add( new Racer(Integer.parseInt(data[0]), Integer.
parseInt(data[1]), 0));
}
List sortByStart = new ArrayList(racers);
Collections.sort(sortByStart, new Comparator() {
public int compare(Racer a, Racer b) {
return a.start - b.start;
}
});
int[] sortByEnd = new int[racers.size()];
for (int i=0; i < racers.size(); ++i) {
Racer racer = racers.get(i);
sortByEnd[i] = racer.end;
}
Arrays.sort(sortByEnd);
TreeSet processedRacer = new TreeSet(new Comparator<
Racer>() {
public int compare(Racer a, Racer b) {
return a.end - b.end;
}
});
for (Racer racer : sortByStart) {
int a = Arrays.binarySearch(sortByEnd, racer.end);
int b = processedRacer.size() - processedRacer.tailSet(racer).
size();
processedRacer.add(racer);
racer.score = a - b;
}
for (Racer racer : racers) {
System.out.println(racer.score);
}
}
}

间

【在 c*********m 的大作中提到】

b*e2015-07-24 07:07

75 楼

(Balanced) Tree that records the size of each subtree in the subroot.

【在 p*****2 的大作中提到】

:
: 哇。太牛了。膜拜一下了。多谢。

x*w2015-07-24 07:07

76 楼

展开说说？？

【在 t*q 的大作中提到】

: 就是求逆序的加强版啊

p*22015-07-24 07:07

77 楼

balanced tree是可以。不过自己写一个还是太麻烦了吧。我是从来没有写过。

【在 b***e 的大作中提到】

: (Balanced) Tree that records the size of each subtree in the subroot.

p*22015-07-24 07:07

78 楼

大牛自己好好体会一下吧。呆鸭子太牛了。

【在 x*********w 的大作中提到】

:
: 展开说说？？

b*e2015-07-24 07:07

79 楼

O(n^2) is trivial. Just to provide a means to O(n*log(n)), which I don't
see other posts providing clearly. Not interested in implementing any sort
of algorithms. The math's interesting, the coding's tedious.

【在 p*****2 的大作中提到】

:
: 大牛自己好好体会一下吧。呆鸭子太牛了。

p*22015-07-24 07:07

80 楼

sort
嗯。算法是不错的。

【在 b***e 的大作中提到】

: O(n^2) is trivial. Just to provide a means to O(n*log(n)), which I don't
: see other posts providing clearly. Not interested in implementing any sort
: of algorithms. The math's interesting, the coding's tedious.

b*e2015-07-24 07:07

81 楼

So much for Mr. Odersky and now coffeescript + node.js?

【在 p*****2 的大作中提到】

:
: sort
: 嗯。算法是不错的。

p*22015-07-24 07:07

82 楼

前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
。

【在 b***e 的大作中提到】

: So much for Mr. Odersky and now coffeescript + node.js?

d*n2015-07-24 07:07

83 楼

Post a O(NlogN) solution.
class Racer
{
public Racer(int id, int start, int end)
{
Id = id;
Start = start;
End = end;
StartRank = 0;
Score = 0;
}

public int Id { get; set; }
public int Start { get; set; }
public int End { get; set; }
public int Score { get; set; }
public int StartRank { get; set; }
}
void RankRacers(Racer[] racers)
{
Array.Sort(racers, (a, b) => a.Start - b.Start);
for (int i = 0; i < racers.Length; ++i)
{
racers[i].StartRank = i;
}
Array.Sort(racers, (a, b) => a.End - b.End);
List StartRanks = new List();
for (int i = 0; i < racers.Length; ++i)
{
// the score is the number of processed racers(ended earlier)
// whose StartRank is higher than current racer.
racers[i].Score = BinarySearchInsert(StartRanks, racers[i].StartRank);
}
Array.Sort(racers, (a, b) => a.Score - b.Score);
}
int BinarySearchInsert(List processedRanks, int startRank)
{
int index = processedRanks.BinarySearch(startRank);
index = (index < 0) ? ~index : index;
int score = processedRanks.Count - index;
processedRanks.Insert(index, startRank);
return score;
}
Hope this helps.

【在 p*****2 的大作中提到】

:
: 前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
: 。

t*q2015-07-24 07:07

84 楼

汗，大家互相吹捧啊

【在 p*****2 的大作中提到】

:
: 前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
: 。

x*w2015-07-24 07:07

85 楼

太厉害了，是怎么想到的

【在 t*q 的大作中提到】

: 汗，大家互相吹捧啊

p*22015-07-24 07:07

86 楼

感觉做过800题也不一定能想到呀。

【在 x*********w 的大作中提到】

:
: 太厉害了，是怎么想到的

g*92015-07-24 07:07

87 楼

弱问下 rf 是哪里。。。。谢谢

w*x2015-07-24 07:07

88 楼

public class RacerScore
{
static public class Segment
{
int id = -1;
int beg = 0;
int end = 0;

Segment(int i, int b, int e)
{
id = i;
beg = b;
end = e;
}
}

static public class comp implements Comparator
{
public int compare(Segment s1, Segment s2)
{
return s1.beg - s2.beg;
}
}

static public void getScores(Segment[] segs, int b, int e, HashMap<
Integer, Integer> mp, Segment[] tmp)
{
if (b >= e) // >= not <
return;

int mid = (b + e)/2;
getScores(segs, b, mid, mp, tmp);
getScores(segs, mid + 1, e, mp, tmp);

int lftIter = b;
int rgtIter = mid + 1;
int iter = 0;
while (lftIter <= mid || rgtIter <= e)
{
if (lftIter <= mid && (rgtIter > e || segs[lftIter].end < segs[
rgtIter].end))
{

if (!mp.containsKey(segs[lftIter].id))
mp.put(segs[lftIter].id, 0);
mp.put(segs[lftIter].id, mp.get(segs[lftIter].id) + rgtIter
- mid - 1);

tmp[iter++] = segs[lftIter++];
}
else
{
tmp[iter++] = segs[rgtIter++];
}
}

for (int i = 0; i <= e - b; i++)
segs[b + i] = tmp[i];
}

static public void printScore(Segment[] segs)
{
if (null == segs)
return;

Arrays.sort(segs, new comp());

HashMap map = new HashMap();
Segment[] tmp = new Segment[segs.length];
getScores(segs, 0, segs.length-1, map, tmp);

Iterator iter = map.keySet().iterator();
while (iter.hasNext())
{
int id = iter.next();
int num = map.get(id);
System.out.println(id + " " + num);
}
}

public static void main(String[] strs)
{
Segment[] segs = new Segment[10];
segs[0] = new Segment(0, 0, 4);
segs[1] = new Segment(1, 1, 3);
segs[2] = new Segment(2, 2, 3);
segs[3] = new Segment(3, 3, 12);
segs[4] = new Segment(4, 4, 6);
segs[5] = new Segment(5, 9, 14);
segs[6] = new Segment(6, 10, 44);
segs[7] = new Segment(7, 12, 32);
segs[8] = new Segment(8, 4, 7);
segs[9] = new Segment(9, 16, 24);

printScore(segs);
}
}

d*n2015-07-24 07:07

89 楼

Added this to my blog at: http://codeanytime.blogspot.com/2013/05/score-of-racers.html

【在 d****n 的大作中提到】

: Post a O(NlogN) solution.
: class Racer
: {
: public Racer(int id, int start, int end)
: {
: Id = id;
: Start = start;
: End = end;
: StartRank = 0;
: Score = 0;

r*n2015-07-24 07:07

90 楼

the most natural method is to first sort the data w.r.t. starting time and
iterate backwards while building a balanced binary search tree to access
rank.
if implemented in c++, the dilemma is that the stl map/set do not provide
rank functionality, you will have to use a combination of lower_bound and
distance to get rank, where distance runs in linear time since map/set do
not have random iterator.
to achieve O(nlogn), you will have to implement balanced bst yourself which
is more difficult than the problem itself.
another approach is to modify the inversion count algorithm:
http://www.geeksforgeeks.org/counting-inversions/
suppose you save data in tuple arr[N] with (start, end, score
). first sort arr w.r.t. start, then use modified merge sort from above
where comparison is w.r.t. end, during the merge step, update score
accordingly.

H*r2015-07-24 07:07

91 楼

这题有oj? 求链接，这两天晚上想玩玩这个题哈

【在 p*****2 的大作中提到】

:
: 感觉做过800题也不一定能想到呀。

p*22015-07-24 07:07

92 楼

你去申请就会得到连接了

H*r2015-07-24 07:07

93 楼

rf 根本不尔我啊 ... :((
有其他的oj么？

【在 p*****2 的大作中提到】

: 你去申请就会得到连接了