PAT 1095. Cars on Campus (30)

思路不難，就是處理起來略繁

查詢的時候題目說明按照時間順序查詢，就暗示要進行前面的record删掉，一開始用STL中的list的erase逾時了，後來用vector記錄上次不滿足條件的起始位址，類似于僞删除

#include<iostream>
#include<vector>
#include<map>
#include<string.h>
#include<string>
#include<list>
#include<algorithm>
#define IN 0
#define OUT 1
using namespace std;
int second[];
struct car{
    int hour, min, sec;
    int time;
    int state;
    string card;
    bool checked;
}node;
struct duration{
    int begin,end;
}item;

struct List{
    struct duration node;
    struct List *next;
}*head, *p,*tail;
vector<struct car> record;
vector<struct duration> rec;
map<string, int> m,t;
vector<string> stored;
vector<int> order[];
list<struct duration>ca;
bool cmp_record(const struct car a, const struct car b){
    return a.time < b.time;
}

void PrintTime(int max){
    int hour, min, sec;
    hour = max / ;
    max -= hour * ;
    min = max / ;
    sec = max - min * ;
    if (hour < )
        printf("0%d:", hour);
    else printf("%d:", hour);
    if (min < )
        printf("0%d:", min);
    else printf("%d:", min);
    if (sec < )
        printf("0%d\n", sec);
    else printf("%d\n",sec);
}

bool cmp_duration(const struct duration &a, const struct duration &b){
    if (a.begin == b.begin)
        return a.end < b.end;
    else return a.begin < b.begin;
}

int main(){
    freopen("1.in", "r", stdin);
    int numofrecord, numofquery;
    cin >> numofrecord >> numofquery;
    int i;
    int hour, min, sec;
    char card[], state[];
    for (i = ; i < numofrecord; i++){
        scanf("%s %d:%d:%d %s", card, &hour, &min, &sec, state);
        node.card = card;
        node.hour = hour;
        node.min = min;
        node.sec = sec;
        node.time = hour *  + min *  + sec;
        node.checked = false;
        if (strcmp(state,"in") == )
            node.state = IN;
        else node.state = OUT;
        record.push_back(node);
    }
    sort(record.begin(), record.end(),cmp_record);
    vector<struct car>::iterator itrecord;
    int j,index;
    int countcar = ;
    head = tail = NULL;
    for (i = ;i<record.size(); i++){
        if (record[i].state == IN)
        {
            if (m[record[i].card]>)
                order[m[record[i].card]-].push_back(i);
            else {
                m[record[i].card] = countcar;
                order[countcar-].push_back(i);
                countcar++;
            }
        }
        else if (record[i].state == OUT&&m[record[i].card]){
            index = m[record[i].card] - ;
            for (j = order[index].size()-; j >= ; j--)
                if (record[order[index][j]].checked == false)
                {
                    record[order[index][j]].checked = true;
                    item.begin = record[order[index][j]].time;
                    item.end = record[i].time;
                    rec.push_back(item);
                    t[record[i].card] += item.end - item.begin;
                    break;
                }
                else break;
        }
    }
    int time = ;
    sort(rec.begin(), rec.end(), cmp_duration);
    int pre = ;
    list<struct duration>::iterator lit;
    vector<struct duration>::iterator rit;
    for (i = ; i < numofquery; i++)
    {
        scanf("%d:%d:%d", &hour, &min, &sec);
        time = hour *  + min *  + sec;
        int count = ;
        while (pre!=rec.size()&&rec[pre].end<=time){
            pre++;
        }
        for (j = pre; j < rec.size(); j++)
            if (time>=rec[j].begin&&time<rec[j].end)
                count++;
            else if (rec[j].begin > time)
                break;
        printf("%d\n", count);
    }
    int max = ;
    map<string, int>::iterator mit;
    for (mit = t.begin(); mit != t.end();mit++)
        if (mit->second>max){
            stored.clear();
            max = mit->second;
            stored.push_back(mit->first);
        }
        else if (mit->second == max){
            stored.push_back(mit->first);
        }
        sort(stored.begin(), stored.end());
        for (i = ; i < stored.size(); i++)
            cout << stored[i] << " ";
        PrintTime(max);
    return ;
}