[PAT解题报告] Cars on Campus

稍微有点麻烦的模拟，模拟停车场。每条记录是时间 hh:mm:ss, 车牌号， in/out。表示车的出入记录。查询一些时间点的车数，求停留时间最长的车（可能很多）。

关键问题是，每辆车的记录可能有问题，比如同一辆车可能有很多连续的in，或者很多连续的out。原则是一辆车很多连续的in只考虑最后一个in，然后只考虑它后面第一个out和它匹配。简单地说很多连续的in最后一个有效，很多连续的out第一个有效。

时间的处理，hh:mm:ss转变为秒数hh * 3600 + mm * 60 + ss, 因为数据都是一天的。我们把记录按照车牌号排序——因为输出停留最长时间的车也是按照车牌号字典顺序输出的。排好顺序后相同车牌的车在一起，再按时间顺序排序。这样同一辆车的记录按照时间顺序排好了。注意相同时间（应该没有）又in又out哪个先都无所谓，因为即使把它们匹配，停留的时间也是0。

在保证车牌照相同的前提下，对同一辆车，先循环找到目前连续的in中最后一个in——忽略它之前所有的out和in。

如果能找到第一个in，再继续找到第一个out,忽略它之前所有的in,其实这里根本没必要循环，因为之前的in是连续的最后一个，所以这个位置显然要么是out，要么是别的车牌，但是为了清晰我还是写了循环——应该不会执行的。

重点就是我写的两个函数givein, giveout，有一个找不到就可以直接退出计算下一辆车了。

然后对同一辆车，它的停留时间是累加的（out time - in time)，并且我们可以用一个大数组a，记录在某个时刻车出入的变化量，in时刻车变化量加1,out时刻车变量减1。

所有的车都处理完后，我们已经知道了哪些车停留的时间最长，并且按照我们处理的顺序，停留时间最长的那些车已经放在数组里了——这个顺序恰好是车牌照的字典序，因为我们是按照车牌照排序的。

还有一个问题就是每个时刻的车数，我们已经记录下来变化量，比如某时刻要加1（不一定是1，同一时刻可能很多车出入），某时刻可能要减1。我们从0到3600 ＊ 24 - 1即从00:00:00到23:59:59秒累加这些变化量就能得到某个时刻的真正车数——其实就一个循环a[i] += a[i - 1]即可。

然后要查询哪个时刻，直接输出那个时刻即可。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

struct node {
char s[10];
int t;
bool in;
};


const int M = 3600 * 24;
int a[M];
vector<node> v;
char s[5];
vector<string> answer;

bool cmp(const node &a, const node &b) {
int c = strcmp(a.s, b.s);
    if (c < 0) {
        return true;
    }
    if (c > 0) {
        return false;
    }
    return a.t < b.t;
}

bool givein(int &i, int j) {
    for (;(i < j) && (!v[i].in); ++i)
    ;
    if (i >= j) {
        return false;
    }
    for (; (i < j) && (v[i].in); ++i)
    ;
    --i;
    return true;
}   

bool giveout(int &i, int j) {
    for (; (i < j) && (v[i].in); ++i)
    ;
    return i < j;
}

int main() {
int n, q;
    scanf("%d%d",&n,&q);
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        int x, y, z;
        scanf("%s %d:%d:%d %s", v[i].s, &x,&y,&z, s);
        v[i].t = x * 3600 + y * 60 + z;
        v[i].in = (s[0] == 'i');
    }
    sort(v.begin(), v.end(), cmp);
    int best = -1;
    for (int i = 0; i < n;) {
        int m;
        for (m = i; (m < n) && (strcmp(v[i].s, v[m].s) == 0); ++m)
        ;
        string name = v[i].s;
        int may = 0;
        for  (may = 0;;) {
            if (!givein(i, m)) {
                break;
            }
            int j = i;
            if (!giveout(i, m)) {
                break;
            }
            ++a[v[j].t];
            --a[v[i].t];
            may += v[i].t - v[j].t;
        }
        if (may > best) {
            best = may;
            answer.resize(1);
            answer[0] = name;
        }
        else if (may == best) {
            answer.push_back(name);
        }
    }
    for (int i = 1; i < M; ++i) {
        a[i] += a[i - 1];
    }
    for (;q;--q) {
        int x, y, z;
        scanf("%d:%d:%d",&x,&y,&z);
        printf("%d\n",a[x * 3600 + y * 60 + z]);
    }
    for (int i = 0; i < answer.size(); ++i) {
        printf("%s ",answer[i].c_str());
    }
    printf("%02d:%02d:%02d\n", best / 3600, best % 3600 / 60, best % 60);
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1095