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 = 1000 + 10;

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 = 0;    

        double total = 0;

        cin >> n;

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

        sort(a, a+n);

        for(int i=0; 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
", total/n);
    }

    return 0;
}