Garage解题报告

IOI2009 Day2

题目叙述

一个停车场里面有N个停车位，编号从1到N。停车场每天开始时是空的然后按照如下规则操作：当一辆车到达停车场的时候，员工检查停车场是否有空车位，如果没有，这辆车会停留在入口直到一个停车位空出来。如果有空停车位，或者直到某个车位空出来了，这辆车会停进那个停车位。如果有多个停车位是空的，这辆车会停在编号最小的车位，如果在有车等待的时候更多的车到达了停车场，他们会按照他们到达的顺序排成一列，然后当有空位出现的时候，队列中的第一辆车会停进那个空位。

停车费用等于车辆的重量乘上停车位的系数，停车费用与停车时间无关。

停车场的操作员知道会有M辆车到达，以及它们到达和离开的顺序。请你帮助他计算停车场能获得的收益。

数据规模

1<=N<=100

1<=M<=2000

解题思路

这个问题的思想就是一个朴素的模拟思想，但其中用到的数据结构却不完全是平凡的。一个简单的不需要任何数据结构的算法应该是遵循如下步骤：

1. 对于每辆车，记录他的状态（不在停车场，在队列，在停车位上），他停放的位置（如果它已经停下来），它的到达时间（如果它在队列中）。

2. 对于每个停车位，记录它是否是空的。

那么现在就可以对输入事件进行处理，当一辆车到达的时候，在停车位中循环找到最小的空位，如果找到了，将车停放在那里，否则车会进入队列，记录他的到达时间。

当一辆车离开的时候，他将会被队列前端的车替代。在所有车中循环，找到一个仍在队列中且到达时间最早的车，如果找到了，将他停在这个空车位上，并记录他已经不在队列中。

以上算法的时间复杂度为O(M2+MN)，它可以通过用一个单独的数组维护队列来优化至O(MN)，然后也可以通过将空车位用二叉堆维护以优化至O(MlogN)。但是，不用这些优化也同样可以拿到满分。

<-->