A27928. 取行李一般机场里，航班到达后，旅客们会去到达区的行李传送带那里取自己的行李。现假设有一座特别的机场，每条传送带只有一个取行李的窗口。旅客们必须排好队，逐一到窗口取自己的行李。但是当某人到窗口前，发现行李不是自己的，那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口，直到它的主人把它取走。假设每一次认领需要 1 分钟，本题就要求你计算传送带清空需要的时间、以及旅客们的平均等待时间。例如，…
填空题
困难
知识点
题目描述
取行李
一般机场里，航班到达后，旅客们会去到达区的行李传送带那里取自己的行李。
现假设有一座特别的机场，每条传送带只有一个取行李的窗口。旅客们必须排好队，逐一到窗口取自己的行李。但是当某人到窗口前，发现行李不是自己的，那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口，直到它的主人把它取走。假设每一次认领需要 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。
输入
输入首先在第一行给出一个正整数 N（≤ 103）。下一行给出 N 个数字，是 [1, N] 区间内整数的一个重排列，表示旅客队列。这里我们假设行李队列是按 1、2、……、N 有序的，并且行李 i 属于旅客 i。一行中数字间以空格分隔。
输出
在一行中输出传送带清空需要的时间、以及旅客们的平均等待时间（输出小数点后 1 位）。数字间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
5
3 5 1 2 4样例输出
9 6.0参考答案
#include<bits/stdc++.h>
using namespace std;
int b[1001]={0};
int main(){
int n;cin>>n;queue<int>a;
for(int i=0;i<n;i++){
int lke;cin>>lke;
a.push(lke);
}
int cnt=0,xli=1;
while(!a.empty()){
cnt++;
int num=a.front();
a.pop();//读入完就把它pop
if(xli!=num){
a.push(num);//不是它就让他到队尾
}
else{
//cout<<num<<" "<<cnt<<endl;//调试用的
b[num]=cnt;
xli++;
}
}
double num=0;
for(int i=1;i<=n;i++){
num+=b[i];
}
cout<<cnt<<" ";printf("%.1lf",num/n);
return 0;
}
上一题
下一题