Salesman
SRM 714 · 2017-02-20 · by lg5293
Problem Statement
There are n people who live on the real axis. The people are numbered 0 through n-1. Person i lives at the position pos[i]. All of these positions are distinct.
Bob is a salesman. He travels along the real axis and he makes trades with the n people who live there. Bob trades items of a single type. Each person has a particular supply or demand of that item. In particular, if delta[i] is positive, the person has a supply of delta[i] units, otherwise the person has a demand of -delta[i] units. It is guaranteed that the sum of all elements of delta is nonnegative.
At the beginning, Bob is at position 0 and he has no items. In one second, he can move left or right by one unit. He can trade with a person if and only if he is exactly at the same position as that person. All trades happen instantly. During each trade Bob can buy or sell as many items as he wants. Of course, he can only sell the items he currently owns. While walking along the real axis, Bob can carry arbitrarily many items at the same time. He can pass through a position with a person without trading with them, if that is what he wants. (he can always come back and trade with them later.)
Bob has a single goal: he wants to trade the items in a way that will satisfy all demands. He can end his travels at any position. Determine and return the smallest amount of time in which Bob can achieve his goal.
Constraints
- pos will have between 1 and 2,500 elements, inclusive.
- delta will have the same number of elements as pos.
- Each element of pos,delta will be between -10^5 and 10^5, inclusive.
- Elements in pos will be distinct and will be strictly increasing.
- The sum of delta will be nonnegative.
{-10,1,100}
{-5,6,-1}
Returns: 122
Here we have three people. Person 0 is at position -10 and has a demand of 5 units. Person 1 is at position 1 and has 6 units of supply. Person 2 is at position 100 and has a demand of 1 unit. In this case, one optimal path for Bob is as follows: First, walk to position 1. Since Bob is at the same position as person 1, he can take all their supply. Next, walk to position -10. Bob can satisfy person 0's demands completely, and will be left with 1 unit remaining. Finally, walk to position 100. Bob can satisfy person 2's demands. At this point, Bob can end his walk. The total cost of this walk is 1+11+110 = 122.
{-10,1,100}
{-5,6,1}
Returns: 12
This time, we don't need to visit the rightmost person.
{-100000,-5,-3,0,3,5,100000}
{123,50,1,-101,1,50,54321}
Returns: 20
It is allowed for a person to be at position 0.
{-10,-5,-4,-3,-2,-1,1,5,6,7,8,9}
{6,-2,1,-2,1,-2,1,-3,1,-2,1,0}
Returns: 29
It is allowed for a person's delta to be zero.
{2018}
{2017}
Returns: 0
Submissions are judged against all 169 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Salesman with a public method int minMoves(vector<int> pos, vector<int> delta) · 169 test cases · 2 s / 256 MB per case