ACM.队列

我就是我 2023-07-05 05:28 10阅读 0赞

## 队列题目 ##

一.报数-队列-约瑟夫环  
Problem:A  
Time Limit:1000ms  
Memory Limit:65535K  
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 <bits/stdc++.h>
    using namespace std;
    int n,m;
    int main()
    {
        
        scanf("%d %d",&n,&m);
        queue<int>vis;
        for(int i=1;i<=n;i++)
        {
        
            vis.push(i);
        }
        while(vis.size()>1)
        {
        for(int j=1;j<m;j++)
        {
        
            int tmp=vis.front();
            vis.pop();
            vis.push(tmp);
        }
        vis.pop();}
        int tp=vis.front();
        printf("%d\n",tp);
        return 0;
    }

二.取牌游戏-队列-SET  
Problem:B  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
小明正在使用一堆共 K 张纸牌与 N-1 个朋友玩取牌游戏。其中，N≤K≤100000，2≤N≤100，K 是 N 的倍数。纸牌中包含 M=K/N 张“good”牌和 K-M 张“bad”牌。小明负责发牌，他当然想自己获得所有“good”牌。  
他的朋友怀疑他会欺骗，所以他们给出以下一些限制，以防小明耍诈：  
1）游戏开始时，将最上面的牌发给小明右手边的人。  
2）每发完一张牌，他必须将接下来的 P 张牌（1≤P≤10）一张一张地依次移到最后，放在牌堆的底部。  
3）以逆时针方向，连续给每位玩家发牌。  
小明迫切想赢，请你帮助他算出所有“good”牌放置的位置，以便他得到所有“good”牌。牌从上往下依次标注为 \#1，\#2，\#3，…  
Input  
第 1 行，3 个用一个空格间隔的正整数 N、K 和 P。  
Output  
M 行，从顶部按升序依次输出“good”牌的位置。(就是从小到大输出)  
Sample Input  
3 9 2  
Sample Output  
3  
7  
8  
读懂题目的意思是关键，发现“good”的牌都发给了小明自己，根据题目描述的N的倍数都 发給了小明自己，所以当K 是N的倍数时，就存入到一个数组当中去。

#include <bits/stdc++.h>
    using namespace std;
    queue<int>vis;
    int a[10001];
    int i;
    int main()
    {
        
        int n,k,p,num=0,q=0;
        cin>>n>>k>>p;
        for(i=1;i<=k;i++)
        {
        
            vis.push(i);
        }
        while(!vis.empty())
        {
        
            int tmp=vis.front();
            vis.pop();
            num++;
            if(num%n==0)a[q++]=tmp;//是n的倍数，说明是good牌
            if(!vis.empty())//执行洗p张牌的操作
            {
        
                for(i=1;i<=p;i++)
                {
        
                    int tp=vis.front();
                    vis.pop();
                    vis.push(tp);
                }
            }}
            sort(a,a+k/n);//排序后输出
            for(i=0;i<k/n;i++)
            {
        
                cout<<a[i]<<endl;
            }
        return 0;
    }

三.酒桌游戏-队列  
Problem:C  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
n个人围成一个圆桌，按照顺时针的顺序1，2，…n进行编号；某一个人开始报一个数字，然后顺时针的下一个人会报数+1；当某个人报的数字含有7或是7的倍数时，这个人退出游戏，其他人接着报数！直到剩下一个人为止！  
Input  
输入n,m,t；n代表人数，m代表开始报数的人的编号；t表示开始报数的人报出的数字是t;  
然后接下来有n行，是这n个人的名字！  
Output  
输出最后一个人的名字！  
Sample Input  
5 3 20  
liming  
wangze  
gongxiangjun  
wangming  
chenzhen  
Sample Output  
chenzhen

#include <bits/stdc++.h>
    using namespace std;
    int i,j;
    struct sa//结构体存储序号和名字
    {
        
        int xuhao;
        char name[100];
    };
    int judge(int q)//判断是否含有7或者是否是7的倍数。
    {
        
        if(q%7==0)
    {
        
    return 0;
    }
    else
    {
        
    int temp = q;
    while(temp>0){
        
    if(temp%10==7){
        
    return 0;
    break;}
    temp = temp /10;
     }
     return 1;
     }
    }
    queue<sa>vis;
    int main()
    {
        
        int n,m,t;
        scanf("%d %d %d",&n,&m,&t);
        struct sa stu[n+1];
        for(i=1;i<=n;i++)
        {
        
            scanf("%s",stu[i].name);
            stu[i].xuhao=i;
        }
        j=t;
        for(i=m;i<=n;i++)//从第m个人开始报数
        {
        
            vis.push(stu[i]);
        }
        for(i=1;i<m;i++)
        {
        
            vis.push(stu[i]);
        }//报数第一圈完成
        while(vis.size()>1)
        {
        for(;judge(j)!=0;j++)
        {
        
            struct sa tmp=vis.front();
            vis.pop();
            vis.push(tmp);
        }
        vis.pop();
        j++;
        }
        printf("%s\n",vis.front().name);
        return 0;
    }

四.海港-队列  
Problem:D  
Time Limit:2000ms  
Memory Limit:65535K  
Description  
小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。  
小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数k,以及每名乘客的国籍x1,x2,x3,x4等；  
小K 统计了这N 艘船的信息，希望你帮助计算出每1艘船到达为止的24小时（86400秒）内到达的船上的乘客来自多少个国家？  
Input  
第1行为一个n,表示有n条船；  
接下来有n行，每行前2个数为t和k,表示这艘船的到达时间和船上的旅客数量！  
然后是这k个旅客的国籍（x1 x2 x3 …都是整数）  
Output  
输出n行，每行代表这艘船到达为止的24小时（86400秒）内到达的船上的乘客来自多少个国家？  
t\[i\]-t\[p\]<86400,t\[i\]表示当前船的时间，t\[p\]表示之前进海港的船！  
1<=n,k<=300000; 1<=ti<=1000000000;  
Sample Input  
例子输入1：  
3  
1 4 4 1 2 2  
2 2 2 3  
10 1 3  
例子输入2：  
4  
1 4 1 2 2 3  
3 2 2 3  
86401 2 3 4  
86402 1 5  
Sample Output  
例子输出1：  
3  
4  
4  
例子输出2：  
3  
3  
3  
4

一艘船上可能有不同国籍的乘客，最后要统计的是国籍的数，不能以船建立结构体，应该以人建立结构体。

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e5+1;
    struct sa
    {
        
        int t;//到达时间
        int x;//国籍编号
    };
    queue<sa>vis;
    int n,t,k,x,ans=0;
    int num[N];
    int main()
    {
        
        struct sa tmp;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
        
            scanf("%d %d",&t,&k);
            for(int j=1;j<=k;j++)
            {
        
                scanf("%d",&x);
                vis.push({
        t,x});
                if(num[x]==0)ans++;//类似桶排序的方法，检测到的是第一个这个国籍的人，总数ans++；
                num[x]++;//代号为x的国籍人数加一。
            }
            while(t-vis.front().t>=86400)//当相差时间超过86400s==一天时，去掉不属于一天范围的人
            {
        
                tmp=vis.front();
                vis.pop();
                int x1=tmp.x;
                num[x1]--;//相应该国家人数减一
                if(num[x1]==0) ans--;//该国家人数归0，国家总数减去一
            }
            printf("%d\n",ans);
        }
        return 0;
    }

五.关系网络-队列  
Problem:E  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
有 n 个人，他们的编号为 1~n，其中有一些人相互认识，现在 x 想要认识 y，可以通过他所认识的人来认识更多的人（如果 a 认识 b，b 认识 c，那么 a 可以通过 b 来认识 c），求出 x 最少需要通过多少人才能认识 y。  
Input  
第 1 行 3 个整数 n、x、y，2≤n≤100；  
接下来的 n 行是一个 n×n 的邻接矩阵，  
a\[i\]\[j\]=1 表示 i 认识 j，a\[i\]\[j\]=0 表示不认识。  
保证 i=j 时，a\[i\]\[j\]=0，并且 a\[i\]\[j\]=a\[j\]\[i\]。  
Output  
一行一个整数，表示 x 认识 y 最少需要通过的人数。数据保证 x 一定能认识 y。  
Sample Input  
5 1 5  
0 1 0 0 0  
1 0 1 1 0  
0 1 0 1 0  
0 1 1 0 1  
0 0 0 1 0  
Sample Output  
2  
用队列实现广度优先搜索。

#include <bits/stdc++.h>
    using namespace std;
    const int N=110;
    int n,bx,ex,vis[N],a[N][N];
    struct node
    {
        
        int x,cnt;//cnt记录移动的步数
    };
    queue<node>q;
    int main()
    {
        
        ios::sync_with_stdio(false);
        cin>>n>>bx>>ex;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            cin>>a[i][j];
        q.push({
        bx,0});//输入起点
        vis[bx]=1;//起点标记
        while(!q.empty())
        {
        
            int x=q.front().x;
            int cnt=q.front().cnt;
            q.pop();
            if(x==ex){
        printf("%d\n",cnt-1);break;}//找到退出
            for(int i=1;i<=n;i++)
            {
        
                if(a[x][i]&&!vis[i])//找到所有x能到达的点
                {
        
                    vis[i]=1;//标记
                    q.push({
        i,cnt+1});//入队
                }
            }
        }
        return 0;
    }

六.Blash数集-队列-set  
Problem:F  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
大数学家高斯小时候偶然间发现一种有趣的自然数集合 Blash ，对应以 a 为基的集合 Ba 定义如下：  
（1）a 是集合 Ba 的基，且 a 是 Ba 的第一个元素。  
（2）如果 x 在集合 Ba 中，则 2x+1 和 3x+1 也都在集合 Ba 中。  
（3）没有其他元素在集合 Ba 中了。  
现在小高斯想知道如果将集合 Ba 中元素按照升序排列，第 n 个元素会是多少？  
Input  
一行输入包括两个数字，集合的基 a 以及所求元素序号 n 。(1<=a<=50,1<=n<=100000)  
Output  
输出第n个元素的值！  
Sample Input  
1 100  
Sample Output  
418  
Hint  
样例2：  
输入： 28 5437  
输出：900585  
类似于暴力枚举例题中的丑数题目，都是在几个元素的基础上构造新的，并且边构造边排序。  
用优先队列会超时。

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n,p2,p3,a[N];
    int main()
    {
        
        ios::sync_with_stdio(false);
        cin>>a[1]>>n;
        p2=1,p3=1;
        for(int i=2;i<=n;i++)
        {
        
            a[i]=min(2*a[p2]+1,3*a[p3]+1);
            if(a[i]==2*a[p2]+1)p2++;
            if(a[i]==3*a[p3]+1)p3++;
        }
        printf("%d\n",a[n]);
        return 0;
    }

七.周末舞会-队列  
Problem:G  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。  
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

白给，签到题。

#include <bits/stdc++.h>
    using namespace std;
    queue<int>vis1,vis2;
    int main()
    {
         int n,m,k,s1,s2;
     cin>>n>>m;
      cin>>k;
      for(int i=1;i<=n;i++)
       {
        vis1.push(i);}
      for(int i=1;i<=m;i++)
        {
        vis2.push(i);}
    for(int i=1;i<=k;i++)
        {
         s1=vis1.front();
    vis1.pop();
    s2=vis2.front();
    vis2.pop();
    cout<<s1<<" "<<s2<<endl;
    vis1.push(s1);
    vis2.push(s2); }
    return 0;
    }