首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13204

取行李 一般机场里,航班到达后,旅客们会去到达区的行李传送带那里取自己的行李。 现假设有一座特别的机场,每条传送带只有一个取行李的窗口。旅客们必须排好队,逐一到…

取行李

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

现假设有一座特别的机场,每条传送带只有一个取行李的窗口。旅客们必须排好队,逐一到窗口取自己的行李。但是当某人到窗口前,发现行李不是自己的,那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口,直到它的主人把它取走。假设每一次认领需要 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 ≈ 3.7。

时间限制:1000

内存限制:65536

输入

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

输出

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


样例输入

5
3 5 1 2 4

样例输出

9 6.0
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; using namespace std; int main() { int N; cin &gt;&gt; N; vector&lt;int&gt; passengers(N); for (int i = 0; i &lt; N; ++i) { cin &gt;&gt; passengers[i]; } queue&lt;int&gt; q; for (int p : passengers) { q.push(p); } int current_luggage = 1; int time = 0; vector&lt;int&gt; wait_time(N + 1, 0); // 使用1-based索引 while (current_luggage &lt;= N) { int p = q.front(); q.pop(); if (p == current_luggage) { time += 1; wait_time[p] = time; current_luggage += 1; } else { time += 1; q.push(p); } } int total_time = time; double sum = 0; for (int i = 1; i &lt;= N; ++i) { sum += wait_time[i]; } double avg = sum / N; cout &lt;&lt; total_time &lt;&lt; " " &lt;&lt; fixed &lt;&lt; setprecision(1) &lt;&lt; avg &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。