StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is basically the maximum subarray sum problem. On the other hand, we can look at it from somewhat different POV. Let us find out where will we have the most deficiency in the fuel if we start the journey from the very first gas station. Since we know that reaching this point shall take the most of the fuel, we can conclude that the truck has to start at this point to minimize the negative fuell balance. Below is the solution with the driver program with O(N) time and O(1) space complexity and there is no need for any DP, since everything is done in a single pass and using only two integers to store the start point index and its value (though this is needed only for printing purposes).</p> <pre><code>#include <stdlib.h> #include <stdio.h> #include <time.h> #include <vector> #include <algorithm> using namespace std; int gasoline[] = {8, 6, 30, 9, 15, 21, 2, 18}; int stations[] = {15, 8, 2, 6, 18, 9, 21, 30}; int rnd_num(const int& low, const int& high) { int rndnum = (int) (((double) rand() / (double) RAND_MAX) * (high - low + 1) + low); return rndnum; } void swap(int data[], const int& idxlow, const int& idxhigh) { int tmp = data[idxlow]; data[idxlow] = data[idxhigh]; data[idxhigh] = tmp; } void print_array(const char* label, int data[], int size) { printf("%-10s: ", label); for (int i = 0; i < size; ++i){ printf("%-3d ", data[i]); } printf("\n"); } void print_vector(const char* label, const vector<int>& data) { printf("%-10s: ", label); for (vector<int>::size_type i = 0; i < data.size(); ++i){ printf("%-3d ", data[i]); } printf("\n"); } void shuffle(int data[], int size) { for (int i = 0; i < size - 1; ++i){ int idx = rnd_num(i + 1, size - 1); swap(data, i, idx); } } void run(int gas[], int dist[], int size) { vector<int> path; int diff = 0, vidx, minidx = 0, minval = gas[0] - dist[0]; path.resize(size); for (int i = 0; i < size; ++i) { diff += gas[i] - dist[i]; if (i == size - 1){ vidx = 0; //path[0] = diff; } else { vidx = i + 1; //path[i + 1] = diff; } path[vidx] = diff; if (diff < minval) { minval = diff; minidx = vidx; } } print_vector("PATHS ", path); printf("MINIDX: %d\nMINVAL: %d\n", minidx, minval); } int main() { int size = sizeof(stations)/sizeof(stations[0]); srand((unsigned)time(NULL)); shuffle(gasoline, sizeof(gasoline)/sizeof(gasoline[0])); shuffle(stations, sizeof(stations)/sizeof(stations[0])); print_array("GASOLINE ", gasoline, sizeof(gasoline)/sizeof(gasoline[0])); print_array("STATIONS ", stations, sizeof(stations)/sizeof(stations[0])); run(gasoline, stations, size); return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload