# 11348: 【原1348】舞会排队

### 题目描述

author: Rui Yang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1348

## Sample Input:

``````2
3 5
8
1 0
2 0
1 1
1 2
2 2
2 2
1 3
2 3
``````

## Sample Output:

``````0.75 0.50
``````

## Sample Input:

``````3
3 5 3
7
1 0
2 0
1 2
2 2
1 7
1 6
1 5
``````

## Sample Output:

``````1.40 0.50
``````

## ligongzzz's solution

``````#include "iostream"
#include "iomanip"
#include "cstdio"
#include "queue"
#include "vector"
using namespace std;

template <class T>
class myPriorityQueue {
vector<T> queueData;
unsigned int sizeOfQueue = 0;
bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

//向下过滤
void percolateDown(unsigned int pos) {
while (pos * 2 <= sizeOfQueue) {
if (pos * 2 + 1 > sizeOfQueue) {
//交换
if (cmp(queueData[pos * 2], queueData[pos])) {
auto temp = queueData[pos * 2];
queueData[pos * 2] = queueData[pos];
queueData[pos] = temp;
}
break;
}
else {
bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
auto temp = queueData[pos * 2 + minNum];
queueData[pos * 2 + minNum] = queueData[pos];
queueData[pos] = temp;
pos = pos * 2 + minNum;
}
else break;
}
}
}

public:
//构建
myPriorityQueue() {
queueData.clear();
queueData.push_back((T)0);
sizeOfQueue = 0;
}

//compare函数返回父结点a与孩子结点b的关系正确与否
myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
queueData.clear();
queueData.push_back((T)0);
sizeOfQueue = 0;
}

//根据数组建立堆
void buildHeap(T *eleData, unsigned int eleNum) {
queueData.clear();
sizeOfQueue = eleNum;
queueData.push_back((T)0);
for (unsigned int i = 1; i <= eleNum; i++)
queueData.push_back(eleData[i - 1]);
//向下过滤
for (unsigned int pos = eleNum / 2; pos > 0; pos--)
percolateDown(pos);
}

//判断是否空
bool empty() {
return sizeOfQueue == 0;
}

//返回队列大小
auto size() {
return sizeOfQueue;
}

//入队
void push(const T& input) {
sizeOfQueue++;
queueData.push_back(input);

//向上过滤
for (auto i = sizeOfQueue; i > 1; i = i / 2) {
//判断是否比父结点更小
if (cmp(queueData[i], queueData[i / 2])) {
//交换
auto temp = queueData[i];
queueData[i] = queueData[i / 2];
queueData[i / 2] = temp;
}
else break;
}
}

//队列最前
T top() {
if (sizeOfQueue == 0)
return NULL;
return queueData[1];
}

//出队
T pop() {
if (sizeOfQueue == 0)
return NULL;
auto temp = queueData[1];
queueData[1] = queueData[sizeOfQueue--];
queueData.pop_back();
percolateDown(1);
return temp;
}
};

int main() {
int N,num;
cin >> N;
int *songTime = new int[N];
for (int i = 0; i < N; i++)
scanf("%d", &songTime[i]);

cin >> num;
myPriorityQueue<int> boy, girl;
int *boytemp = new int[num+1], *girltemp = new int[num+1],boyNum=0,girlNum=0;
for (int i = 0; i < num; i++) {
int sex;
scanf("%d", &sex);
if (sex == 1)
scanf("%d", &boytemp[boyNum++]);
else
scanf("%d", &girltemp[girlNum++]);
}
//建立队列
boy.buildHeap(boytemp, boyNum);
delete boytemp;
girl.buildHeap(girltemp, girlNum);
delete girltemp;

double boyTotal = 0, girlTotal = 0;

for (long long currentTime = 0, i = 0;
i < N;
currentTime += songTime[i], i++) {
//最后一首歌，大家一起来
if (i == N - 1) {
while (!boy.empty())
boyTotal += currentTime - boy.pop();
while (!girl.empty())
girlTotal += currentTime - girl.pop();
}
//配对CP
else {
while (!boy.empty() && !girl.empty() && boy.top() <= currentTime&&girl.top() <= currentTime) {
boyTotal += currentTime - boy.pop();
girlTotal += currentTime - girl.pop();
}
}
}

//输出
printf("%.2f %.2f",boyTotal / boyNum,girlTotal / girlNum);
delete songTime;
return 0;
}
``````

## Neight99's solution

``````#include <iomanip>
#include <iostream>

using namespace std;

int lengths[100100] = {0}, boyTimes[1000100], girlTimes[1000100];

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 = 10000000);
~seqQueue();
bool isEmpty() const;
void enQueue(const elemType &);
elemType deQueue();
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>
return data[(front + 1) % maxSize];
}

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

void qSort(int *, int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N, people, currentSong = 0, currentTime = 0, boySum = 0, girlSum = 0;
double boyWait = 0, girlWait = 0;
seqQueue<int> boys, girls;

cin >> N;
for (int i = 0; i < N; i++) {
cin >> lengths[i];
}

cin >> people;
for (int i = 0; i < people; i++) {
int tmp, times1;
cin >> tmp >> times1;
if (tmp == 1) {
boyTimes[boySum] = times1;
boySum++;
} else if (tmp == 2) {
girlTimes[girlSum] = times1;
girlSum++;
}
}

qSort(boyTimes, 0, boySum - 1);
qSort(girlTimes, 0, girlSum - 1);

for (int i = 0; i < boySum; i++) {
boys.enQueue(boyTimes[i]);
}
for (int i = 0; i < girlSum; i++) {
girls.enQueue(girlTimes[i]);
}

for (int currentSong = -1; currentSong < N; currentSong++) {
if (currentSong == -1) {
currentTime = 0;
} else if (currentSong == N - 2) {
currentTime += lengths[currentSong];
while (!boys.isEmpty()) {
boyWait += currentTime - boys.deQueue();
}
while (!girls.isEmpty()) {
girlWait += currentTime - girls.deQueue();
}
break;
} else {
currentTime += lengths[currentSong];
}

while (!boys.isEmpty() && !girls.isEmpty() &&
boyWait += currentTime - boys.deQueue();
girlWait += currentTime - girls.deQueue();
}
}
cout << setiosflags(ios::fixed) << setprecision(2) << (boyWait / boySum)
<< ' ' << (girlWait / girlSum);

return 0;
}

void qSort(int *num, int l, int h) {
if (l >= h) {
return;
}
int first = l, last = h, key = num[first];

while (first < last) {
while (first < last && num[last] >= key) {
--last;
}
num[first] = num[last];
while (first < last && num[first] <= key) {
++first;
}
num[last] = num[first];
}
num[first] = key;
qSort(num, l, first - 1);
qSort(num, first + 1, h);
}
``````

## Pangbo13's solution

``````#include<queue>
#include<iostream>
using namespace std;
int main(){
int N,M;
int maleNum = 0,femaleNum = 0;
priority_queue <int,vector<int>,greater<int>> male;
priority_queue <int,vector<int>,greater<int>> female;
scanf("%d",&N);
int* song = new int[N];
for(int i = 0;i<N;i++) scanf("%d",&song[i]);
scanf("%d",&M);
int sex,time;
for(int i = 0;i<M;i++){
scanf("%d%d",&sex,&time);
switch(sex){
case 1:
male.push(time);
maleNum++;
break;
case 2:
female.push(time);
femaleNum++;
break;
}
}
long currentTime = 0;
long femaleWaitTime = 0,maleWaitTime = 0;
for(int i = 0;i<N-1;i++){
if(female.empty()||male.empty()){
currentTime += song[i];
continue;
}
while(female.top()<=currentTime&&male.top()<=currentTime){
femaleWaitTime += currentTime - female.top();
maleWaitTime += currentTime - male.top();
female.pop();
male.pop();
if(female.empty()||male.empty()) break;
}
currentTime += song[i];
}
while(!female.empty()){
femaleWaitTime += (currentTime - female.top());
female.pop();
}
while(!male.empty()){
maleWaitTime += (currentTime - male.top());
male.pop();
}
double femaleAvgWaitTime,maleAvgWaitTime;
maleAvgWaitTime = (double)maleWaitTime/maleNum;
femaleAvgWaitTime = (double)femaleWaitTime/femaleNum;
delete[] song;
printf("%.2lf %.2lf",maleAvgWaitTime,femaleAvgWaitTime);
}
``````

## q4x3's solution

``````/**
* 大模拟好啊
* 看清题目
* 一群基佬跳什么舞呢nmsl
**/
#include <iostream>
#include <stdio.h>
#include <iomanip>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

long long N, len[100233], qm[2000233], qf[2000233], M, mal, fem, tmps, tmpt, curt;
double ans1, ans2;

int main() {
scanf("%lld", &N);
for(int i = 0;i < N;++ i) {
scanf("%lld", &len[i]);
}
scanf("%lld", &M);
for(int i = 0;i < M;++ i) {
scanf("%lld%lld", &tmps, &tmpt);
if(tmps == 1) qm[mal ++] = tmpt;
else qf[fem ++] = tmpt;
}
mergeSort(0, mal, qm);
mergeSort(0, fem, qf);
for(int i = 0;i < N - 1;++ i) {
}
curt += len[i];
}
for(int i = mhead;i < mal;++ i) {
malt += (curt - qm[i]);
}
for(int i = fhead;i < fem;++ i) {
femt += (curt - qf[i]);
}
if(mal == 0) {
ans1 = 0;
} else {
ans1 = malt / (double)mal;
}
if(fem == 0) {
ans2 = 0;
} else {
ans2 = femt / (double)fem;
}
cout << fixed << setprecision(2) << ans1 << " " << ans2 << endl;
}
``````

## victrid's solution

``````#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;
int timelist[100005] = {0};
int man[1000001];
int woman[1000001];
int* MergeSort(int* list, int listSize) {
if (listSize == 1)
return list;
if (listSize == 2) {
if (list[0] > list[1]) {
int temp = list[0];
list[0]  = list[1];
list[1]  = temp;
return list;
}
return list;
}
int* tmplist = new int[listSize];
int* llst    = MergeSort(list, listSize / 2);
int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
int lct = 0, rct = 0;
while (lct + rct != listSize) {
if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
tmplist[lct + rct] = llst[lct];
lct++;
} else {
tmplist[lct + rct] = rlst[rct];
rct++;
}
}
memcpy(list, tmplist, sizeof(int) * listSize);
delete[] tmplist;
return list;
}
int main() {
int N, M;
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &timelist[i]);
scanf("%d", &M);
int mann = 0, frau = 0, proc;
for (int i = 0; i < M; i++) {
scanf("%d", &proc);
if (proc == 1)
scanf("%d", &man[mann++]);
else
scanf("%d", &woman[frau++]);
}

MergeSort(man, mann);
MergeSort(woman, frau);

int
current_time   = 0,
*man_current   = man,
*woman_current = woman,
*man_end       = man + mann,
*woman_end     = woman + frau;
double
man_wasted   = 0,
woman_wasted = 0;

for (int i = 0; i < N; i++) {
man_wasted += current_time - *man_current;
woman_wasted += current_time - *woman_current;
man_current++;
woman_current++;
}
current_time += timelist[i];
}
current_time -= timelist[N-1];
while (man_current != man_end) {
man_wasted += current_time - *man_current;
man_current++;
}
while (woman_current != woman_end) {
woman_wasted += current_time - *woman_current;
woman_current++;
}
cout << setiosflags(ios::fixed) << setprecision(2);
cout << man_wasted / (double)mann << ' ' << woman_wasted / (double)frau;
return 0;
}
``````