寂寞的订书钉城市 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

寂寞的订书钉城市

寂寞的订书钉城市# Joke - 肚皮舞运动

x*02012-11-12 08:11

1 楼

Suppose there is a circle. There are n petrol pumps on that circle. You are
given two sets of data.
1. The amount of petrol that petrol pump will give.
2. Distance from that petrol pump to the next petrol pump.
Calculate the first point from where a truck will be able to complete the
circle (The truck will stop at each petrol pump and it has infinite capacity
). Expected time complexity is O(n). Assume for 1 litre petrol, the truck
can go 1 unit of distance.
For example, let there be 4 petrol pumps with amount of petrol and distance
to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The
first point from where truck can make a circular tour is 2nd petrol pump.
Output should be “start = 1″ (index of 2nd petrol pump).
这道似乎是一经典老题。
大家知道怎么解的么？

x*o2012-11-12 08:11

2 楼

l*i2012-11-12 08:11

3 楼

这个看起来像算法课的作业题

H*g2012-11-12 08:11

4 楼

good

j*y2012-11-12 08:11

5 楼

int indexToStart(pair A[], int n)
{
int lowestGasInTheTank = 0;
int gasInTheTank = 0;
int index = 0;
for(int i = 1; i < n ; ++i)
{
gasInTheTank += A[i - 1].first - A[i - 1].second;
if(lowestGasInTheTank > gasInTheTank)
{
lowestGasInTheTank = gasInTheTank;
index = i;
}
}
gasInTheTank += A[n - 1].first - A[n - 1].second;
if(lowestGasInTheTank > gasInTheTank)
{
lowestGasInTheTank = gasInTheTank;
index = 0;
}
return index;
}

are
capacity
distance

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

: Suppose there is a circle. There are n petrol pumps on that circle. You are
: given two sets of data.
: 1. The amount of petrol that petrol pump will give.
: 2. Distance from that petrol pump to the next petrol pump.
: Calculate the first point from where a truck will be able to complete the
: circle (The truck will stop at each petrol pump and it has infinite capacity
: ). Expected time complexity is O(n). Assume for 1 litre petrol, the truck
: can go 1 unit of distance.
: For example, let there be 4 petrol pumps with amount of petrol and distance
: to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The