Skip to content

11207: 【原1207】ferry

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1207

Description

本题题意对于书上内容有变动,“设车辆到达服从均匀分布,参数由用户指定”改为“输入数据给出每辆车的到达时间”。

Input Format

第一行含有一个正整数N(1<=N<=20000),代表总车辆数。

第二行到第N+1行,每行包含两个整数p,q.(0<=p<=1,0<=q<=100000)。p代表车辆类型,0代表客车,1代表货车。q代表到达时间(单位为分钟)。

Output Format

输出包含两个数a,b。代表客车和货车的平均等待时间,精确到小数点后三位。

Sample Input1

9
0 1
1 2
0 3
1 4
0 5
0 7
0 9
0 11
1 11

Sample Output1

5.667 7.667

Sample Input2

11
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0 
0 0
1 0
1 0

Sample Output2

1.111 0.000

Limits

1.输入数据保证q递增(即不用对输入数据进行排序)。

2.对于任何合法输入数据,答案是唯一的。

3.“四辆客车后可上一辆货车”对每艘渡轮分开计算。

ligongzzz's solution

#include "iostream"
#include "queue"
#include "iomanip"
using namespace std;

int main() {
    queue<int> car;
    queue<int> truck;

    //输入
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int temp,arrive;
        scanf("%d %d", &temp, &arrive);
        if (temp == 0)
            car.push(arrive);
        else
            truck.push(arrive);
    }

    long long carTime = 0, truckTime = 0;
    int carNum = car.size(), truckNum = truck.size();

    //开始模拟
    for (int t = 0;!car.empty()||!truck.empty(); t += 10) {
        //上船
        for (int n = 0,carn=0; n < 10; n++) {
            if (!car.empty()&&car.front() <= t && !truck.empty()&&truck.front() <= t) {
                if (carn< 4) {
                    carTime += t-car.front();
                    car.pop();
                    carn++;
                }
                else {
                    truckTime += t-truck.front();
                    truck.pop();
                    carn = 0;
                }
            }
            else if (!car.empty()&&car.front() <= t) {
                carTime += t-car.front();
                car.pop();
                carn++;
            }
            else if (!truck.empty()&&truck.front() <= t) {
                truckTime += t-truck.front();
                truck.pop();
            }
        }
    }

    printf("%.3f %.3f",(double)carTime / (double)carNum, (double)truckTime / (double)truckNum);

    return 0;
}

Neight99's solution

#include <iomanip>
#include <iostream>

using namespace std;

template <class elemType>
class queue {
   public:
    virtual bool isEmpty() const = 0;
    virtual void enQueue(const elemType &) = 0;
    virtual elemType deQueue() = 0;
    virtual elemType getHead() const = 0;
    virtual ~queue() {}
};

template <class elemType>
class seqQueue : public queue<elemType> {
   private:
    elemType *data;
    int maxSize;
    int front, rear;
    void doubleSpace();

   public:
    seqQueue(int size = 5);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &);
    elemType deQueue();
    elemType getHead() const;
    int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = data;
    data = new elemType[maxSize * 2];

    for (int i = 1; i <= maxSize; i++) {
        data[i] = tmp[(front + i) % maxSize];
    }

    front = 0;
    maxSize *= 2;
    delete tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
    data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
    delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
    return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    if ((rear + 1) % maxSize == front) {
        doubleSpace();
    }
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;
    return data[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
    return ((rear + maxSize - front) % maxSize);
}

int main() {
    int n, nCoach = 0, nTruck = 0, type, time1, totalTime, currentTime = 0;
    double coachTime = 0, truckTime = 0;
    seqQueue<int> q1, q2;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> type >> time1;
        if (!type) {
            q1.enQueue(time1);
            nCoach++;
        } else {
            q2.enQueue(time1);
            nTruck++;
        }
    }

    while (!(q1.isEmpty() && q2.isEmpty())) {
        int coachOnFerry = 0, allOnFerry = 0;

        while (allOnFerry < 10) {
            if (!q1.isEmpty() && q1.getHead() <= currentTime) {
                if (coachOnFerry < 4) {
                    coachTime += currentTime - q1.deQueue();
                    coachOnFerry++;
                    allOnFerry++;
                } else if (!q2.isEmpty() && q2.getHead() <= currentTime) {
                    truckTime += currentTime - q2.deQueue();
                    allOnFerry++;
                    coachOnFerry = 0;
                } else {
                    coachTime += currentTime - q1.deQueue();
                    allOnFerry++;
                    coachOnFerry++;
                }
            } else if (!q2.isEmpty() && q2.getHead() <= currentTime) {
                truckTime += currentTime - q2.deQueue();
                allOnFerry++;
                coachOnFerry = 0;
            } else {
                break;
            }
        }
        currentTime += 10;
    }

    cout << setiosflags(ios::fixed) << setprecision(3) << coachTime / nCoach
         << ' ' << truckTime / nTruck;
}

yyong119's solution

#include <cstdio>
using namespace std;

class queue {
private:
    int *data, front, back, maxSize;

    void doubleSpace() {
        int *tmp = new int[maxSize << 1];
        for (int i = 1; i < maxSize; ++i)
            tmp[i] = data[(front + i) % maxSize];
        front = 0;
        back = maxSize - 1;
        maxSize <<= 1;
        delete [] data;
        data = tmp;
    }
public:
    queue(int initSize = 10) : maxSize(initSize), front(0), back(0) {
        data = new int[maxSize];
    }
    ~queue() {
        delete [] data;
    }
    void enQueue(int n) {
        if ((back + 1) % maxSize == front) doubleSpace();
        back = (back + 1) % maxSize;
        data[back] = n;
    }
    int deQueue() {
        front = (front + 1) % maxSize;
        return data[front];
    }
    int getHead() {
        return data[(front + 1) % maxSize];
    }
    bool isEmpty() {
        return front == back;
    }
};

int main() {

    int N; scanf("%d", &N);
    queue q0, q1;
    int carType, arriveTime;
    int sum0 = 0, sum1 = 0, cnt0 = 0, cnt1 = 0, timer = 0;
    for (int i = 0; i < N; ++i) {
        scanf("%d%d", &carType, &arriveTime);
        if (carType == 0) {
            q0.enQueue(arriveTime);
            ++cnt0;
        }
        else {
            q1.enQueue(arriveTime);
            ++cnt1;
        }
    }
    for (timer = 0; !q0.isEmpty() || !q1.isEmpty(); timer += 10) {
        int ship = 0;
        for (; ship < 8 && !q0.isEmpty() && q0.getHead() <= timer; ++ship)
            sum0 += timer - q0.deQueue();
        for (; ship < 10 && !q1.isEmpty() && q1.getHead() <= timer; ++ship)
            sum1 += timer - q1.deQueue();
        for (; ship < 10 && !q0.isEmpty() && q0.getHead() <= timer; ++ship)
            sum0 += timer - q0.deQueue();
    }
    printf("%.3f %.3f\n", double(sum0) / cnt0, double(sum1) / cnt1);
    return 0;
}