SDUT2087 离散事件模拟-银行管理(模拟)

题目链接。

分析：

模拟。

果然模拟什么的最讨厌了。

用e1，e2分别记录队列1，队列2的结束时间。

每个结点的s记录开始时间，e一开是记录逗留时间，进队列的时候，改成离开的时间。时刻记录总时间就可以了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxn =  + ;

struct node {

    double s, e;

    bool operator < (const node &rhs) const {

        return s < rhs.s;

    }

    bool operator > (const node &rhs) const {   //greater要用到，即小顶堆

        return s > rhs.s;

    }

}a[maxn];

double e1, e2;

int main() {

    int T, n;

    cin >> T;

    while(T--) {

        priority_queue<node, vector<node>, greater<node> > Q1, Q2;  //两个小顶堆

        e1 = e2 = ;    

        double total = ;

        cin >> n;

        for(int i=; i<n; i++) cin >> a[i].s >> a[i].e;

        sort(a, a+n);

        for(int i=; i<n; i++) {

            while(!Q1.empty() && Q1.top().e <= a[i].s)

                Q1.pop();

            while(!Q2.empty() && Q2.top().e <= a[i].s)

                Q2.pop();

            if(Q1.size() <= Q2.size()) {

                if(a[i].s < e1) {

                    e1 += a[i].e;

                    a[i].e = e1;

                    total += a[i].e - a[i].s;

                }

                else {

                    e1 = a[i].s + a[i].e;

                    total += a[i].e;

                    a[i].e = a[i].s + a[i].e;

                }

                Q1.push(a[i]);

            }

            else {

                if(a[i].s < e2) {

                    e2 += a[i].e;

                    a[i].e = e2;

                    total += a[i].e - a[i].s;

                }

                else {

                    e2 = a[i].s + a[i].e;

                    total += a[i].e;

                    a[i].e = a[i].s + a[i].e;

                }

                Q2.push(a[i]);

            }

        }

        printf("%.2lf\n", total/n);

    }

    return ;

}

SDUT2087 离散事件模拟-银行管理(模拟)的相关教程结束。