高程实验8队列
1. (程序题, 30分) 周末舞会
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。
Input
第 1 行两个正整数，表示男士人数 m 和女士人数 n，1≤m，n≤1000；
第 2 行一个正整数，表示舞曲的数目 k，k≤1000。
Output
共 k 行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。
Sample Input
2 4
6
Sample Output
1 1
2 2
1 3
2 4
1 1
2 2
int main()
{
int m,n,i,x,k,y;
queue<int >man;
queue<int >woman;
cin>>m>>n;
for(i=1;i<=m;i++)
{
man.push(i);
}
for(i=1;i<=n;i++)
{
woman.push(i);
}
cin>>k;
for(i=1;i<=k;i++)
{
cout<<man.front()<<" "<<woman.front()<<endl;
x=man.front();
y=woman.front();
man.pop();
woman.pop();
man.push(x);
woman.push(y);
}
return 0;
}2. (程序题, 35分) 约瑟夫环
Description
n个小朋友们坐成一个圆圈，编号分别为1，2，3.....n；第1个小朋友从1开始报数，报到m的小朋友离开座位；然后下一个小朋友从1接着报数；直到剩下最后一个小朋友为止；
Input
输入2个数字n和m;（1<=n,m<=1000）
Output
输出最后一个小朋友的编号！
Sample Input
10 5
Sample Output
3
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n,m,i,x,num=0;
cin>>n>>m;
queue<int>q;
for(i=1;i<=n;i++)
{
q.push(i);
}
while(q.size()>1)
{
x=q.front();
num++;
if(num==m){q.pop();num=0;}
else{q.pop();q.push(x);}
}
cout<<q.front()<<endl;
return 0;
}
Description
林大食堂非常拥挤，得排队买饭，陈老师也是一样的！
有n个人在一个卖饭窗口前排队买饭，假如每个人买饭的时间为t,请编程找出一种这n个人排队的顺序，使得这n个人的平均等待时间最小。如果两个人的打饭时间相同，则原来排在前面的，还是在前面。
Input
第一行一个n(1<=n<=1000),
第2行分别表示每人的打饭时间t1,t2,t3,......tn，1<=t[i]<=10000；
Output
第1行为排队顺序；
第2行为平均等待时间（结果保留2位小数）；
Sample Input
10
56 12 1 99 1000 234 33 55 99 812
Sample Output
3 2 7 8 1 4 9 6 10 5
291.90
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;
struct sa
{
int time;
int id;
};
bool operator <(const sa &a,const sa &b)
{
if(a.time!=b.time)
return a.time>b.time;
else
return a.id>b.id;
}
int main()
{
priority_queue<sa>pq;
int n,x;
double sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
pq.push({x,i});
}
struct sa tmp;
for(int i=1;i<=n;i++)
{
tmp=pq.top();
if(i!=n)
cout<<tmp.id<<" ";
else
cout<<tmp.id<<endl;
sum+=(n-i)*tmp.time;
pq.pop();
}
printf("%.2lf\n",sum/n);
return 0;
}