题目描述

一般机场里，航班到达后，旅客们会去到达区的行李传送带那里取自己的行李。

现假设有一座特别的机场，每条传送带只有一个取行李的窗口。旅客们必须排好队，逐一到窗口取自己的行李。但是当某人到窗口前，发现行李不是自己的，那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口，直到它的主人把它取走。假设每一次认领需要 1 分钟，本题就要求你计算传送带清空需要的时间、以及旅客们的平均等待时间。

例如，假设行李 i 属于旅客 i 。行李的到达顺序是 1、2、3，旅客的到达顺序是 2、1、3。则 1 号行李要等 2 分钟才能被主人 1 号旅客取走。这时行李队列中有 2、3，旅客队列中是 3、2。于是 2 号行李还要等 2 分钟才能被 2 号旅客取走，最后 3 号在第 5 分钟取走行李。旅客们的平均等待时间是 (2 + 4 + 5) / 3 \approx 3.7 。

输入格式

输入首先在第一行给出一个正整数 N (\le 10 ^ 3) 。下一行给出 N 个数字，是 [1,N] 区间内整数的一个重排列，表示旅客队列。这里我们假设行李队列是按 1、2、……、 N 有序的，并且行李 i 属于旅客 i 。一行中数字间以空格分隔。

输出格式

在一行中输出传送带清空需要的时间、以及旅客们的平均等待时间（输出小数点后 1 位）。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例

5
3 5 1 2 4

输出样例

9 6.0

题意

思路

代码

void solve(){
    int n;
    cin >> n;
    queue<int> q;
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        q.push(x);
    }
    int now = 1; // 当前需要彻底出队的编号 or 当前在窗口的行李
    int time = 0;
    double ave = 0;
    while(q.size()){ // 一次认领 需要一分钟
        time++; // 给时间加一分钟
        if(now == q.front()){ // 当行李编号和队头人的编号一样
            now++; // 拿走行李
            q.pop(); // 走人
            ave += time;
        }else{
            q.push(q.front()); // 重新到队尾排队
            q.pop();
        }
    }
    cout << time << " " << fixed << setprecision(1) << ave / n;
}