[PAT-A] 1095 Cars on Campus

Java

测试点1、2、4、5超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static int n, m;
    static Map<String, List<Event>> cars = new HashMap<>();

    static int get(List<Event> v) {
        int res = 0;
        for (int i = 0; i < v.size(); i += 2) {
            res += v.get(i + 1).time - v.get(i).time;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            String id = line[0];
            String[] timeParts = line[1].split(":");
            int hh = Integer.parseInt(timeParts[0]);
            int mm = Integer.parseInt(timeParts[1]);
            int ss = Integer.parseInt(timeParts[2]);
            String status = line[2];

            int t = hh * 3600 + mm * 60 + ss;
            int s = 0;
            if (status.charAt(0) == 'o') s = 1;

            cars.computeIfAbsent(id, k -> new ArrayList<>()).add(new Event(t, s));
        }

        List<Event> events = new ArrayList<>();
        for (Map.Entry<String, List<Event>> entry : cars.entrySet()) {
            List<Event> v = entry.getValue();
            Collections.sort(v);
            List<Event> newV = new ArrayList<>();

            for (int i = 0; i < v.size(); i++) {
                if (v.get(i).status == 0) {
                    if (i + 1 < v.size() && v.get(i + 1).status == 1) {
                        newV.add(v.get(i));
                        newV.add(v.get(i + 1));
                        i++;
                    }
                }
            }

            v.clear();
            v.addAll(newV);
            events.addAll(v);
        }

        Collections.sort(events);

        int i = 0, sum = 0;
        while (m-- > 0) {
            String[] timeParts = br.readLine().split(":");
            int hh = Integer.parseInt(timeParts[0]);
            int mm = Integer.parseInt(timeParts[1]);
            int ss = Integer.parseInt(timeParts[2]);
            int t = hh * 3600 + mm * 60 + ss;

            while (i < events.size() && events.get(i).time <= t) {
                if (events.get(i).status == 0) sum++;
                else sum--;
                i++;
            }

            System.out.println(sum);
        }

        int maxTime = 0;
        for (Map.Entry<String, List<Event>> entry : cars.entrySet()) {
            maxTime = Math.max(maxTime, get(entry.getValue()));
        }

        List<String> res = new ArrayList<>();
        for (Map.Entry<String, List<Event>> entry : cars.entrySet()) {
            if (get(entry.getValue()) == maxTime) {
                res.add(entry.getKey());
            }
        }

        Collections.sort(res);

        for (String it : res) System.out.print(it + " ");
        System.out.printf("%02d:%02d:%02d\n", maxTime / 3600, maxTime % 3600 / 60, maxTime % 60);
    }
}

class Event implements Comparable<Event> {
    int time, status;

    public Event(int time, int status) {
        this.time = time;
        this.status = status;
    }

    @Override
    public int compareTo(Event other) {
        return Integer.compare(this.time, other.time);
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

struct Event {
    int time, status;

    bool operator<(const Event &t) const {
        return time < t.time;
    }
};

int n, m;
unordered_map <string, vector<Event>> cars;

int get(vector <Event> &v) {
    int res = 0;
    for (int i = 0; i < v.size(); i += 2)
        res += v[i + 1].time - v[i].time;
    return res;
}

int main() {
    scanf("%d%d", &n, &m);

    char id[10], status[10];
    for (int i = 0; i < n; ++i) {
        int hh, mm, ss;
        scanf("%s %d:%d:%d %s", id, &hh, &mm, &ss, status);

        int t = hh * 3600 + mm * 60 + ss;
        int s = 0;                        // in  0
        if (status[0] == 'o') s = 1;    // out 1

        cars[id].push_back({t, s});
    }

    vector <Event> events;

    for (auto &car: cars) {
        auto &v = car.second;
        sort(v.begin(), v.end());
        vector <Event> new_v;

        for (int i = 0; i < v.size(); ++i)
            if (v[i].status == 0) {
                if (i + 1 < v.size() && v[i + 1].status == 1) {
                    new_v.push_back(v[i]);
                    new_v.push_back(v[i + 1]);
                    ++i;
                }
            }

        v = new_v;
        for (auto i: v) events.push_back(i);
    }

    sort(events.begin(), events.end());

    int i = 0, sum = 0;
    while (m--) {
        int hh, mm, ss;
        scanf("%d:%d:%d", &hh, &mm, &ss);
        int t = hh * 3600 + mm * 60 + ss;

        for (; i < events.size() && events[i].time <= t; ++i) {
            if (events[i].status == 0) sum++;        // in
            else sum--;                                // out
        }

        printf("%d\n", sum);
    }

    int maxt = 0;
    for (auto &car: cars) {
        maxt = max(maxt, get(car.second));
    }

    vector <string> res;
    for (auto &car: cars)
        if (get(car.second) == maxt)
            res.push_back(car.first);

    sort(res.begin(), res.end());

    for (auto it: res) cout << it << " ";
    printf("%02d:%02d:%02d\n", maxt / 3600, maxt % 3600 / 60, maxt % 60);

    return 0;
}