1853-zbj的游戏 ZCMU
程序员文章站
2022-03-22 22:16:28
...
Description
这天zbj跟小伙伴们玩了一个游戏,他们总共有n个人,有一条长凳,上面最多能坐m个人。
zbj和他的小伙伴们按照1-n编号,然后按顺序坐上长凳,然后每次长凳上的第k个那个人会被out当一个人被out之后,下一个人就可以坐上长凳,而每个人有自己喜欢的数字ai,他就会坐在第ai个位置。重复步骤直到长凳上的人数小于k
现在zbj想知道,他们这群人的out顺序是怎么样的?
Input
多组输入数据。对于每组输入数据,第一行是两个整数n,m,k(1<=m<n<=11000 1<=k<=m)。接下来一行有n-m个整数ai(1<=ai<=m),按顺序代表站着的人喜爱的数字。
Output
输出out的顺序,输出为一行,每两个数字之间用空格隔开,行末无空格。
Sample Input
5
2 2 1 2 2
Sample Output
2 1 4 5
HINT
比如5个人玩游戏,长凳上只能坐2个人,k=2,那么1号2号先坐在了凳子上,第一轮,2号被out,3号坐下,3号喜欢的数字是1,那么3号坐在了第一个位置上,当前长凳上的顺序变成了3号 1号;第二轮,1号被out,4号坐下,4号喜欢的数字是2,那么4号坐在第二个位置上,当前长凳上的顺序变成了3号 4号;第三轮,4号被out,5号坐下,5号喜欢的数字是2,当前长凳上的顺序变成了3号 5号;第四轮,5号被out,无人坐下;第五轮,当前长凳上只有1个人<k,所以无人能被out,所以游戏结束。
out顺序为2 1 4 5
思路
其实就是用vector容器的删除和插入操作实现该游戏
代码
#include<bits/stdc++.h>
#define MAX 20000
using namespace std;
int main()
{
int n,m,k,i;
while(~scanf("%d%d%d",&n,&m,&k))
{
int pre[MAX];
for(i=m+1;i<=n;i++)
{
scanf("%d",&pre[i]);
}
vector<int> p;
for(i=1;i<=m;i++)
{
p.push_back(i);
}
int flag=0;
for(i=m+1;i<=n;i++)
{
if(!flag)
{
printf("%d",*(p.begin()+k-1));
flag=1;
}
else
printf(" %d",*(p.begin()+k-1));
p.erase(p.begin()+k-1);
p.insert(p.begin()+pre[i]-1,i);
}
while(p.size()>=k)
{
printf(" %d",*(p.begin()+k-1));
p.erase(p.begin()+k-1);
}
printf("\n");
}
return 0;
}
上一篇: Vector真的是线程安全的吗
下一篇: vector的简单实现