好&有趣的队列问题。 [英] Good & Interesting Queue Problem.

问题描述

车库



停车库有n个停车位，编号从1到n（含）。车库每天早晨都空着，全天以下列方式运营。每当汽车到达车库时，服务员会检查是否有可用的停车位。如果没有，那么汽车在入口处等待，直到释放停车位。如果有停车位，或者只要有停车位，则将车停在可用的停车位。如果有多个可用停车位，则车辆将停放在数量最少的空间。如果有更多的汽车在一些汽车等待的时候到达，他们都按照他们到达的顺序在入口处排队。然后，当停车位变得可用时，队列中的第一辆车（即最早到达的车）停在那里。



停车费用美元是以千克为单位的汽车重量乘以其停车位的具体比率。费用并不取决于汽车停在车库的时间长度。



车库操作员知道今天会有m辆车来，他知道他们的订单到达和离开。帮助他计算今天他的收入将达到多少美元。



编写一个程序，根据停车位的具体费率，计算汽车的重量和汽车到达和离开的顺序，以美元确定车库的总收入。







输入



第一行包含两个整数 - 停车位数n（1≤n ≤100）和车辆的数量m（1≤m≤2000），以空格分隔。



接下来的n行描述了停车位的费率。这些线的第s个包含一个整数rs（1≤rs≤100），停车位数s以美元/千克为单位。



下一个m行描述了汽车的重量。这些车的编号从1到m（包括1和m），没有特别的顺序。这些m行中的第k个包含一个整数wk（1≤wk≤10,000），车身k的重量（千克）。



接下来的2m行描述所有汽车的到达和离开按时间顺序排列。正整数i表示车号i到达车库。负整数-i表示车号i离开车库。在车库到达之前，没有车将离开车库，所有从1到m的车辆将在此序列中出现两次，一旦到达并且一旦离开。此外，停车前车辆不会离开车库（即等候排队时没有车会离开）。



输出



一个整数 - 将通过以下方式获得的总金额今天的车库操作员。





输入：

样品1

3 4

2

3

5

200

100

300

800

3

2

-3

1

4

-4

-2

-1



样品2

2 4

5 br />
2

100

500

$

2000

3

1

2

4

-1

-3 < br $>
-2

-4





OUTPUT



样品1

5300



样本2

16200

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.


INPUT :
Sample 1
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

Sample 2
2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4


OUTPUT

Sample 1
5300

Sample 2
16200

推荐答案

我们不做你的作业：它是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。



亲自尝试，你可能会发现它不是和你想的一样困难！

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

这篇关于好&amp;有趣的队列问题。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！