Skip to content

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