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;
}