PAT A1095 Cars on Campus (30 分) 排序

      題目大意：統計校園内某一時刻的車輛數。給出N條記錄，每條記錄包括 車牌、記錄時間 和 狀态(in/out)。然後給出K個時刻，查詢每個時刻的總車輛數，這K個時刻是按照時間遞增順序給出的。與PAT A1016 Phone Bills相同，對于同一輛車而言，隻有在時間上相鄰且狀态不同的兩條記錄被認為是有效的。與PAT A1016不同的是，本題資料量非常大，需要仔細優化。 

       核心問題還是有效記錄的擷取，這裡由于時間隻起到比較大小的作用，可以直接統一化成以秒為機關進行比較。然後對所有記錄先按車牌排序，再按時間排序。滿足同一車牌、時間相鄰、狀态不同的兩條記錄是有效的。

       然後就是要考慮如何查詢能夠不逾時。我采取的辦法是，設立一個以秒為機關的數組change[ ]記錄每個時刻的車輛變化情況，大小是 23*3600+59*60+59，大約是87000。然後在記錄 in / out 有效資訊的同時，對change[ ]中的這兩個位置的元素進行+1和-1的操作。這樣，在沒有車輛開入和開出的時刻，change中對應的位置仍然是0。然後開始查詢，因為查詢時間是遞增的，是以可以利用上一次查詢的結果，即 本次查詢的結果 = 上次查詢的結果 + [上次查詢時間 + 1(s) ~ 本次查詢時間] 的範圍内 change的元素和。注意這裡的範圍是 上次查詢時間+1s，否則會出現重複計算的問題。

      還有輸出最大停留時間的車輛的資訊，這裡為了避免逾時，不用先記錄車輛資訊再排序的方式， 而是在擷取有效資訊的同時，對 車輛的總停留時間 和 全部車輛的最大停留時間 也需要更新，最後隻需要周遊map，擷取停留時間是 最大停留時間 的車輛即可。

AC代碼如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>

using namespace std;

const int MAXN = 87000;
int change[MAXN] = {0};
int totalTime[10010] = {0};

struct record
{
    string name;
    int time;
    int status;
    record(string name, int time, int status)
    {
        this->name = name;
        this->time = time;
        this->status = status;
    }
    bool operator< (const record& another)
    {
        if(this->name != another.name) return this->name < another.name;
        else return this->time < another.time;
    }
};

map<string, int> mpCar;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<record> v, validRecord;
    for (int i = 0; i < N; ++i)
    {
        char name[10], status[10];
        int h, m, s;
        scanf("%s %d:%d:%d %s", name, &h, &m, &s, status);
        v.push_back(record(string(name), h * 3600 + m * 60 + s, status[0] == 'i' ? 1 : -1));
    }
    sort(v.begin(), v.end());
    int i = 0;
    int maxTime = 0;
    while(i < v.size() - 1)
    {
        if(v[i].name == v[i+1].name && v[i].status == 1 && v[i+1].status == -1)
        {
            validRecord.push_back(v[i]);
            validRecord.push_back(v[i+1]);
            mpCar[v[i].name] += v[i+1].time - v[i].time;
            if(mpCar[v[i].name] > maxTime) maxTime = mpCar[v[i].name];
            change[v[i].time]++;
            change[v[i+1].time]--;
            i++;
        }
        i++;
    }

    int count = 0;
    int lastTime = 0;
    for (int query = 0; query < K; ++query)
    {
        int h, m, s;
        scanf("%d:%d:%d", &h, &m, &s);
        int time = h * 3600 + m * 60 + s;
        for (int j = lastTime; j <= time; ++j)
        {
            count += change[j];
        }
        printf("%d\n", count);
        lastTime = time + 1;
    }

    vector<string> vNames;
    for(map<string, int>::iterator it = mpCar.begin(); it != mpCar.end(); it++)
    {
        if(it->second == maxTime) vNames.push_back(it->first);
    }
    sort(v.begin(), v.end());
    for (int j = 0; j < vNames.size(); ++j)
    {
        printf("%s ", vNames[j].c_str());
    }
    printf("%02d:%02d:%02d", maxTime/3600, maxTime%3600/60, maxTime%3600%60);
    return 0;
}