11348: 【原1348】舞会排队
题目
题目描述
author: Rui Yang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1348
Description
为了促进学校男女生之间的交流，学校组织了一个“周末共舞”活动，男生和女生分别排队等待入场。每一首新曲开始，舞池中的同学都会离开场地，正在排队的同学中男生女生从队头进入相同数量，并且尽可能多的同学搭配成舞伴一起入场。每一位同学只跳舞一首曲子的长度，每首曲子长度不同。到最后一首曲子，还未跳过舞的同学们会都进入场地一起跳舞。
请输出男生队伍和女生队伍的平均等待时间分别是多少。
Input Format
第一行：N首曲目（N<100000）
第2行：每一首曲子的长度li
第3行：整个过程将有M个人进入队列(M<1000000)
第4~N+3行：每一行包含每一位到达同学的信息si，第一个数字代表性比：1-男，2-女；第二个数字代表到达时间ti，其中数字0视为第一首乐曲开始时恰好进入，无等待时间。到达时间不会晚于第n首曲目开始的时间。
Output Format
两个两位小数，为所有男生、所有女生的平均等待时间.
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();
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);
}
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() &&
boys.getHead() <= currentTime &&
girls.getHead() <= currentTime) {
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;
long long mhead, fhead, malt, femt;
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) {
while(qm[mhead] <= curt && qf[fhead] <= curt && mhead < mal && fhead < fem) {
malt += (curt - qm[mhead]);
femt += (curt - qf[fhead]);
++ mhead;
++ fhead;
}
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_qhead = man,
*woman_qhead = woman,
*man_end = man + mann,
*woman_end = woman + frau;
double
man_wasted = 0,
woman_wasted = 0;
for (int i = 0; i < N; i++) {
while (*man_qhead <= current_time && man_qhead != man_end)
man_qhead++;
while (*woman_qhead <= current_time && woman_qhead != woman_end)
woman_qhead++;
while (man_current != man_qhead && woman_current != woman_qhead) {
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;
}