[PAT-A] 1017 Queueing at Bank

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    static final int OPEN_TIME = 8 * 3600;
    static final int CLOSE_TIME = 17 * 3600;

    static class Person implements Comparable<Person> {
        int arriveTime;
        int serviceTime;

        Person(int arriveTime, int serviceTime) {
            this.arriveTime = arriveTime;
            this.serviceTime = serviceTime;
        }

        @Override
        public int compareTo(Person t) {
            return Integer.compare(this.arriveTime, t.arriveTime);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> windows = new PriorityQueue<>();
        for (int i = 0; i < k; ++i) {
            windows.add(OPEN_TIME);
        }

        Person[] persons = new Person[n];
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            String[] timeParts = st.nextToken().split(":");
            int hh = Integer.parseInt(timeParts[0]);
            int mm = Integer.parseInt(timeParts[1]);
            int ss = Integer.parseInt(timeParts[2]);
            int serviceMinute = Integer.parseInt(st.nextToken());

            int arriveTime = hh * 3600 + mm * 60 + ss;
            int serviceTime = serviceMinute * 60;
            persons[i] = new Person(arriveTime, serviceTime);
        }

        Arrays.sort(persons);

        int sum = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            Person person = persons[i];
            int window = windows.poll();

            if (person.arriveTime > CLOSE_TIME) {
                break;
            }

            int startTime = Math.max(window, person.arriveTime);
            sum += startTime - person.arriveTime;
            cnt++;

            window = startTime + Math.min(person.serviceTime, 3600); // 从开始办理时间开始算
            windows.add(window);
        }

        System.out.printf("%.1f", sum / 60.0 / cnt);
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 10010, INF = 1e7 + 10;

int n, k;

struct Person {
    int arrive_time;
    int service_time;

    bool operator<(const Person &t) const {
        return arrive_time < t.arrive_time;
    }
} persons[MAXN];

priority_queue<int, vector<int>, greater<int> > windows;

int main() {
    cin >> n >> k;
    for (int i = 0; i < k; ++i) windows.push(8 * 3600);
    for (int i = 0; i < n; ++i) {
        int hh, mm, ss, service_minute;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &service_minute);

        persons[i].arrive_time = hh * 3600 + mm * 60 + ss;
        persons[i].service_time = service_minute * 60;
    }

    sort(persons, persons + n);

    int sum = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        auto person = persons[i];
        auto window = windows.top();
        windows.pop();

        if (person.arrive_time > 17 * 3600) break;

        int start_time = max(window, person.arrive_time);
        sum += start_time - person.arrive_time;
        cnt++;

        window = start_time + min(person.service_time, 1 * 3600); // 从开始办理时间开始算！！！
        windows.push(window);
    }

    printf("%.1lf", sum / 60.0 / cnt);
    return 0;
}