x*****0
发帖数: 452 | 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).
这道似乎是一经典老题。
大家知道怎么解的么？ | l***i
发帖数: 1309 | | j*****y
发帖数: 1071 | 3 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
|
|
