2025寒假算法练习——Week 7

2025-02-22 · 5 分钟阅读 · 数据结构队列递归 ·

复制链接:

文章目录

习题均来自 NEFU OJ

Problem 1632 | 周末舞会-队列

Description

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。

Input

第 1 行两个正整数，表示男士人数 m 和女士人数 n，1≤m，n≤1000；
第 2 行一个正整数，表示舞曲的数目 k，k≤1000。

Output

共 k 行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。

Sample Input

12 4
26

Sample Output

用队列反而时空消耗大，不如直接取模。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        try (Scanner sc = new Scanner(System.in)) {
 6            int m = sc.nextInt();
 7            int n = sc.nextInt();
 8            int k = sc.nextInt();
 9            for (int i = 0; i < k; i++) {
10                System.out.println(String.format("%d %d", i % m + 1, i % n + 1));
11            }
12        }
13    }
14}

Problem 1633 | 取牌游戏-队列-SET

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

13 9 2

Sample Output

13
27
38

直接模拟发牌过程，把小明拿到的牌排序输出。可以用优先队列存储小明拿到的牌，这样就不用单独排序了。

 1import java.util.Scanner;
 2import java.util.Queue;
 3import java.util.LinkedList;
 4import java.util.PriorityQueue;
 5
 6public class Main {
 7    public static void main(String[] args) {
 8        try (Scanner sc = new Scanner(System.in)) {
 9            int N = sc.nextInt();
10            int K = sc.nextInt();
11            int P = sc.nextInt();
12
13            Queue<Integer> queue = new LinkedList<>();
14            PriorityQueue<Integer> result = new PriorityQueue<>();
15            for (int i = 1; i <= K; i++) {
16                queue.offer(i);
17            }
18
19            while (!queue.isEmpty()) {
20                for (int i = 0; i < N - 1; i++) {
21                    queue.poll();
22                    for (int j = 0; j < P; j++) {
23                        queue.offer(queue.poll());
24                    }
25                }
26                result.offer(queue.poll());
27                if (queue.isEmpty()) {
28                    break;
29                }
30                for (int j = 0; j < P; j++) {
31                    queue.offer(queue.poll());
32                }
33            }
34
35            while (!result.isEmpty()) {
36                System.out.println(result.poll());
37            }
38        }
39    }
40}

Problem 1634 | 报数-队列-约瑟夫环

Description

n个小朋友们坐成一个圆圈，编号分别为1，2，3.....n；第1个小朋友从1开始报数，报到m的小朋友离开座位；然后下一个小朋友从1接着报数；直到剩下最后一个小朋友为止；

Input

输入2个数字n和m;（1<=n,m<=1000）

Output

输出最后一个小朋友的编号！

Sample Input

110 5

Sample Output

最直接的暴力做法就是把整个过程模拟一下：

 1import java.util.Scanner;
 2import java.util.Queue;
 3import java.util.LinkedList;
 4
 5public class Main {
 6    public static void main(String[] args) {
 7        try (Scanner sc = new Scanner(System.in)) {
 8            int n = sc.nextInt();
 9            int m = sc.nextInt();
10
11            Queue<Integer> queue = new LinkedList<>();
12            for (int i = 1; i <= n; i++) {
13                queue.offer(i);
14            }
15
16            while (queue.size() > 1) {
17                for (int i = 0; i < m - 1; i++) {
18                    queue.offer(queue.poll());
19                }
20                queue.poll();
21            }
22            System.out.println(queue.peek());
23        }
24    }
25}

当然约瑟夫环问题也有递推公式解法，当最初有 $n$ 人报数，报到 $m$ 的人出列时，最后留下来的人的编号 $f(n,m)=(f(n-1,m)+m)\space mod\space n$。这一公式也不难理解，当第一次有人报数到 $m$ 且出列时，剩余的人刚好组成一个有 $n-1$ 人报数的约瑟夫环，而排头的位置刚好向后移动了 $m$ 个，同时为了防止越界需要对 $n$ 取模。当 $n=1$ 时，$f(1,m)=0$。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        try (Scanner sc = new Scanner(System.in)) {
 6            int n = sc.nextInt();
 7            int m = sc.nextInt();
 8            System.out.println(josephus(n, m) + 1);
 9        }
10    }
11
12    public static int josephus(int n, int m) {
13        if (n == 1) {
14            return 0;
15        } else {
16            return (josephus(n - 1, m) + m) % n;
17        }
18    }
19}

另一种时空开销更小的方法是递推。最后留下来的人一定在每一轮都留下来了，而且在只剩一个人时其编号为 0，因此可以倒推出其每一轮的编号，一直到报数开始前。递推公式为 $k_i=(k_{i-1}+m)\space mod\space i$，$k_i$ 表示某人在倒数第 $i$ 轮开始前的编号，也是倒数第 $i$ 轮结束后的剩余人数。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        try (Scanner sc = new Scanner(System.in)) {
 6            int n = sc.nextInt();
 7            int m = sc.nextInt();
 8
 9            int ans = 0;
10            for (int i = 1; i <= n; i++) {
11                ans = (ans + m) % i;
12            }
13            System.out.println(ans + 1);
14        }
15    }
16}

Problem 1635 | 酒桌游戏-队列

Description

n个人围成一个圆桌，按照顺时针的顺序1，2，...n进行编号；某一个人开始报一个数字，然后顺时针的下一个人会报数+1；当某个人报的数字含有7或是7的倍数时，这个人退出游戏，其他人接着报数！直到剩下一个人为止！

Input

输入n,m,t；n代表人数，m代表开始报数的人的编号；t表示开始报数的人报出的数字是t; 然后接下来有n行，是这n个人的名字！

Output

输出最后一个人的名字！

Sample Input

15 3 20
2liming
3wangze
4gongxiangjun
5wangming
6chenzhen

Sample Output

1chenzhen

 1import java.util.Scanner;
 2import java.util.Queue;
 3import java.util.LinkedList;
 4
 5public class Main {
 6    public static void main(String[] args) {
 7        try (Scanner sc = new Scanner(System.in)) {
 8            int n = sc.nextInt();
 9            int m = sc.nextInt();
10            int t = sc.nextInt();
11            sc.nextLine();
12
13            int i;
14            String[] names = new String[n];
15            i = 0;
16            while (i < n) {
17                names[i++] = sc.nextLine();
18            }
19
20            Queue<String> queue = new LinkedList<>();
21            i = 0;
22            while (i < n) {
23                queue.offer(names[(i++ + m - 1) % n]);
24            }
25
26            while (queue.size() > 1) {
27                if (t % 7 == 0 || String.valueOf(t).contains("7")) {
28                    queue.poll();
29                } else {
30                    queue.offer(queue.poll());
31                }
32                t++;
33            }
34            System.out.println(queue.peek());
35        }
36    }
37}

Problem 1636 | 海港-队列

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：

13
21 4 4 1 2 2
32 2 2 3
410 1 3

例子输入2：

14
21 4 1 2 2 3
33 2 2 3
486401 2 3 4
586402 1 5

Sample Output

例子输出1：

13
24
34

例子输出2：

Hint

NOIP

思来想去，还是用结构体最快最方便。可以把题目理解为，每一位乘客会在岸上待一整天然后离开。首先用结构体存储每一位乘客的上岸时间和国籍，然后再这些结构体存储到队列里，同时用哈希表存储不同国籍的游客数量。每当有船抵达时就判断队首的乘客是否该走了。题目默认 t 遂输入递增。

 1#include <cstdio>
 2#include <map>
 3#include <queue>
 4
 5using namespace std;
 6
 7struct passenger {
 8    int nationality;
 9    int time;
10};
11
12int main() {
13    queue<passenger> passengers;
14    map<int, int> nationalities;
15    int nationality_count = 0;
16
17    int n;
18    scanf("%d", &n);
19
20    while (n--) {
21        int t, k;
22        scanf("%d %d", &t, &k);
23        while (k--) {
24            passenger p;
25            p.time = t;
26            scanf("%d", &p.nationality);
27            nationalities[p.nationality]++;
28            if (nationalities[p.nationality] == 1) {
29                nationality_count++;
30            }
31            passengers.push(p);
32        }
33
34        while (!passengers.empty() && passengers.front().time <= t - 86400) {
35            passenger p = passengers.front();
36            passengers.pop();
37            nationalities[p.nationality]--;
38            if (nationalities[p.nationality] == 0) {
39                nationality_count--;
40            }
41        }
42        printf("%d\n", nationality_count);
43    }
44
45    return 0;
46}

用 cin 和 cout 会超时。