291. Garage
A parking
garage has n parking spaces, numbered
from 1 to n inclusive. The garage
opens empty each morning and operates in the following way throughout the day.
Whenever a car arrives at the garage, the attendants check whether there are
any parking spaces available. If there are none, then the car waits at the
entrance until a parking space is released. If a parking space is available, or
as soon as one becomes available, the car is parked in the available parking
space. If there is more than one available parking space, the car will be
parked at the space with the smallest number. If more cars arrive while some
car is waiting, they all line up in a queue at the entrance, in the order in
which they arrived. Then, when a parking space becomes available, the first car
in the queue (i.e., the one that arrived the earliest) is parked there.
The cost of
parking in dollars is the weight of the car in kilograms multiplied by the
specific rate of its parking space. The cost does not depend on how long a car
stays in the garage.
The garage
operator knows that today there will be m cars coming and he knows the order of
their arrivals and departures. Help him calculate how many dollars his revenue
is going to be today.
Write a
program that, given the specific rates of the parking spaces, the weights of
the cars and the order in which the cars arrive and depart, determines the
total revenue of the garage in dollars.
Input. The first line contains two
integers – the number of parking spaces n
(1 ≤ n ≤ 100) and the
number of cars m (1 ≤ m ≤ 2,000), separated by a space.
The next n
lines describe the rates of the parking spaces. The s-th of these lines contains a single integer rs (1 ≤ rs
≤ 100), the rate of parking space number s in dollars per kilogram.
The next m
lines describe the weights of the cars. The cars are numbered from 1 to m inclusive in no particular order. The k-th of these m lines contains a single integer wk (1 ≤ wk
≤ 10,000), the weight of car k
in kilograms.
The next 2m
lines describe the arrivals and departures of all cars in chronological order.
A positive integer i indicates that
car number i arrives at the garage. A
negative integer -i indicates that
car number i departs from the garage.
No car will depart from the garage before it has arrived, and all cars from 1
to m inclusive will appear exactly
twice in this sequence, once arriving and once departing. Moreover, no car will
depart from the garage before it has parked (i.e., no car will leave while
waiting on the queue).
Output. One integer – the total number of
dollars that will be earned by the garage operator today.
|
Sample input |
Sample output |
|
3 4 2 3 5 200 100 300 800 3 2 -3 1 4 -4 -2 -1 |
5300 |
data structures
Using data
structures, simulate the process of car movement. Store information
about empty parking spaces in the set s.
Thus, the search for a free parking lot with the lowest number will be
performed in O(log2n). For each car,
using the map structure, remember the parking space where it was parked.
When the car leaves, in O(log2n) it is possible to find the parking number
that it frees up.
Since the entrance and the exit of a car
from the parking lot is simulated in O(log2n),
the total running time of the algorithm is O(mlog2n).
Store the cost of
parking spaces in the array price, and
the car weights in the array weight. The
set s stores the numbers of
empty parking places. Thus s.begin() contains the free parking
place with minimum number. In the map mp store the information about the cars that are parked. Equality mp[car] = ParkingPlace means that car with number car is parked
in the place number ParkingPlace. Store the queue
of cars waiting for parking spaces in queue d.
int
price[101], weight[2001];
set<int>
s;
map<int,int> mp;
deque<int>
d;
Read the
input data.
scanf("%d %d",&n,&m);
Add a list of
free parking spaces to the
set s. Initially, all parking
lots from 1 to n are free.
for(i
= 1; i <= n; i++) s.insert(i);
Read the cost of parking spaces and
weights of vehicles.
for(i
= 1; i <= n; i++) scanf("%d",&price[i]);
for(i
= 1; i <= m; i++) scanf("%d",&weight[i]);
Sequentially
read and process the
commands about the arrival and departure of the cars.
for(res
= 0, i = 1; i <= 2 * m; i++)
{
scanf("%d",&car);
The car drives into the parking lot.
if (car >
0)
{
If the set of
free parking spaces s is not empty,
then there is at least one place where the car can be parked.
if
(!s.empty())
{
Assign ParkingPlace to the smallest number of
free parking space.
ParkingPlace = *s.begin();
Add the parking lot profit to the result res.
res += weight[car] * price[ParkingPlace];
A car just
arrived at the place s.begin(). Mark it as used – remove it from the set s.
s.erase(s.begin());
A car number car has just been parked at the place number ParkingPlace.
mp[car] = ParkingPlace;
} else
{
There are no
free parking spaces, put the car in queue d.
d.push_back(car);
}
}
else
Consider the case when car
< 0. The car number -car departs from the lot number mp[-car]. The number of the parking lot
where the car with number -car is
located can be found with
complexity O(log2n)
using the map mp.
{
ParkingPlace = mp[-car];
If there is a
queue of waiting cars, then you should move the first car in the queue to the newly vacated place ParkingPlace.
if
(!d.empty())
{
car = d[0];
res += weight[car] * price[ParkingPlace];
mp[car] = ParkingPlace;
d.pop_front();
}
else
If there is no
one in the queue, then free up the parking space ParkingPlace.
s.insert(ParkingPlace);
}
}
Print the total profit
of the garage operator.
printf("%d\n",res);