Luggage Pickup PTA（栈和队列的使用）

题目

When a flight arrives, the passengers will go to the Arrivals area to pick up their baggage from a luggage conveyor belt （行李传送带）.

Now assume that we have a special airport that has only one pickup window for each conveyor belt. The passengers are asked to line up to pick up their luggage one by one at the window. But if one arrives at the window yet finds out that one is not the owner of that luggage, one will have to move to the end of the queue and wait for the next turn. At the mean time, the luggage at the window will wait until its owner picks it up. Suppose that each turn takes 1 minute, your job is to calculate the total time taken to clear the conveyor belt, and the average waiting time for the passengers.

For example, assume that luggage i belongs to passenger i. If the luggage come in order 1, 2, 3, and the passengers come in order 2, 1, 3. Luggage 1 will wait for 2 minutes to be picked up by passenger 1. Then the luggage queue contains 2 and 3, and the passenger queue contains 3 and 2. So luggage 2 will wait for 2 minutes to be picked up by passenger 2. And finally 3 is done at the 5th minute. The average waiting time for the passengers is (2+4+5)/3≈3.7.

输入格式

Each input file contains one test case. The first line gives a positive integer N (≤10
3
). Then N numbers are given in the next line, which is a permutation of the integers in [1,N], representing the passenger queue. Here we are assuming that the luggage queue is in order of 1, 2, ..., N, and the i-th luggage belongs to passenger i.

All the numbers in a line are separated by a space.

输出格式

For each test case, print in a line the total time taken to clear the conveyor belt, and the average waiting time for the passengers (output 1 decimal place). The numbers must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.

输入样例

5
3 5 1 2 4

输出样例

9 6.0

代码

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<vector>
using namespace std;
int main() {
    int i, j, k, m, n;
    cin >> m;
    vector<int> v;
    queue<int> q;
    for (i = 0; i < m; i++) {
        cin >> n;
        v.push_back(n);
        q.push(n);
    }
    int sum = 0, count = 0;
    for (i = 1; i <= m; i++) {
        n = q.front();
        int cnt = 0;
        while (n != i) {
            q.push(q.front());
            cnt++;
            q.pop();
            n = q.front();
        }
        q.pop();
        count += cnt + 1;
        sum += (m - i + 1) * (cnt+1);
    }
    printf("%d %.1f", count, sum / (float)m);
    return 0;
}