算法刷题整理合集（七）·【算法赛】

本篇博客旨在记录自已的算法刷题练习成长，里面注有详细的代码注释以及和个人的思路想法，希望可以给同道之人些许帮助。本人也是算法小白，水平有限，如果文章中有什么错误或遗漏之处，望各位可以在评论区指正出来，各位共勉💪。

1、抓住拿国一

蓝桥杯赛场上，选手小王脑洞大开，跑去问裁判：“裁判，蓝桥杯要是改成‘蓝桥抓猪大赛’，得抓多少头猪才能拿国一啊？”裁判愣了愣，但为了显摆幽默，淡定答道：“好说！想拿国一，从第一届开始，每届抓的猪数得是这一届的届数加上前面所有届数的总和。比如，第一届抓 1 头，第二届抓 1+2=3 头，第三届抓 1+2+3=6 头 … 今年是第十六届蓝桥杯，你自己算算吧！”

现在，请你帮小王算算，要拿国一，总共得抓多少头猪？

解题代码：

public class Main {public static void main(String[] args) {int sum = 0;for (int i = 1; i <= 16; i++) {sum += i;}System.out.println(sum);}
}

2、蓝桥字符

蓝桥杯官方近日收到了一份神秘的包裹，里面包含一个 U 盘和一张纸条，纸条上仅写有一个由小写字母组成的字符串 S。经过初步检查，U盘内存储的内容似乎与即将到来的蓝桥杯大赛有关，但 U 盘被加密，无法直接访问。根据情报提供方的提示，U盘的密码与字符串 S 中特定子序列的出现次数密切相关。

具体来说，密码等于字符串 S 中子序列 lan 的出现次数。这里的子序列是指从字符串 S 中按顺序选取字符（不一定连续）组成的新字符串。

为了帮助蓝桥杯官方顺利解开 U 盘的密码，你需要编写一个程序，计算字符串 S 中子序列 lan 的出现次数。

输入格式：

输入为一个由小写字母组成的字符串 S，长度不超过 10⁵。

输出格式：

输出一个整数，表示字符串 S 中子序列 lan 的出现次数。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();sc.close();long countL = 0;long countLA = 0;long countLAN = 0;for (char c : s.toCharArray()){if (c == 'l'){countL++;} else if (c == 'a'){countLA += countL;} else if (c == 'n') {countLAN += countLA;}}System.out.println(countLAN);}
}

3、蓝桥大使

小蓝和小桥是某学校的蓝桥大使，他们的主要任务是作为宣传人员在校内宣传蓝桥杯比赛。蓝桥杯是一项全国性的编程竞赛，吸引了众多学生参与。为了扩大比赛的影响力，学校决定在每个班级进行宣传，而小蓝和小桥则负责这项工作。

学校共有 n 个班级，每个班级都需要进行宣传。小蓝和小桥可以选择去不同的班级宣传，但为了公平起见，他们决定尽量平均分配任务。具体来说：

• 小蓝将去 （n/2)个班级宣传。
• 小桥将去剩下的 n−(n/2)个班级宣传。

对于第 i 个班级：

• 如果小蓝去宣传，他将获得 A_i 元的酬劳。
• 如果小桥去宣传，她将获得 B_i 元的酬劳。

小蓝和小桥希望最大化他们总共获得的酬劳，请你帮他们计算总酬劳最大值是多少？

输入格式:

第一行包含一个整数 n(1≤n≤10⁵)，表示班级的数量。

接下来 n 行，每行包含两个整数 A_i,B_i(1≤A_i,B_i≤10⁹)，分别表示小蓝和小桥去第 i 个班级宣传时获得的酬劳。

输出格式：

输出一个整数表示答案。

解题代码：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];int[] b = new int[n];int[] c = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();b[i] = sc.nextInt();c[i] = b[i] - a[i];}sc.close();// 小桥去班宣传的酬劳减去小蓝的，并进行排序Arrays.sort(c);long sum = 0;// 将大于的一半累加，剩下的小蓝去宣传for (int i = n-1; i >= n/2 ; i--) {sum += c[i];}for (int i = 0; i < n; i++) {sum += a[i];}System.out.println(sum);}
}

4、拳头对决

蓝桥训练营的日子总是紧张而充实。某天清晨，队员们在连续的高强度训练后，个个眉头紧锁，烦躁在空气中弥漫，甚至有人开始攥紧拳头，想要找个出口释放压力。蓝教练和红教练察觉到这股暗流，交换了一个眼神，灵光一闪：何不来一场“拳头对决赛”？既能让大家舒展筋骨，又能在笑声中拉近彼此的距离。

拳头的大小，成了这场友谊赛的焦点——谁的拳头大，谁就更有气势！两位教练各挑了 N 名队员，蓝队的第 i 个队员的拳头大小为 A_i，红队的第 i 个队员的拳头大小为 B_i。

比赛的流程是这样的：红教练会按照顺序依次派出他的队员（先派第一位，然后第二位，以此类推）。每当红教练派出一名队员展示拳头后，蓝教练需要从他尚未上场的队员中选择一位应战。裁判会将蓝教练派出的队员的拳头大小与红教练所有已上场队员的拳头大小逐一比较。每当蓝队员的拳头大小大于红队某位已上场队员的拳头，蓝教练便能赢得一次胜利（注意，这不是一对一的较量，而是以一敌多的挑战）。

这场比赛不为胜负，只为放松与切磋，可蓝教练心里却藏着小算盘：既要让队员们开心，也想借机秀一把带队本事，在蓝桥杯的训练营里留下点名声。现在，请你助蓝教练一臂之力，算出在最优策略下，他最多能拿下多少次胜利？

输入格式：

第一行包含一个整数 N（1≤N≤10⁵），表示队员数量。

第二行包含 N 个整数 A₁,A₂,…,A_N（1≤A_i≤10⁹），分别是蓝教练队员的拳头大小。

第三行包含 N 个整数 B₁,B₂,…,B_N（1≤B_i≤10⁹），分别是红教练队员的拳头大小。

输出格式：

输出一个整数，表示蓝教练在最多能赢下的胜利次数。

解题代码：

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = (int)1e5+10;int n = sc.nextInt();int[] a = new int[N];int[] b = new int[N];for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}for (int i = 1; i <= n; i++) {b[i] = sc.nextInt();}sc.close();// 对数组a从索引1到n的部分进行排序Arrays.sort(a,1,n+1);long ret = 0;// 遍历数组for (int i = 1; i <= n; i++) {// 初始化左右指针和答案int l = i,r = n, ans = n+1;// 使用二分查找找到第一个大于b[i]的元素位置while(l <= r) {// 计算中间位置，相当于（l+r）/2int mid = l+r >> 1;if (a[mid] > b[i]){// 如果中间元素大于b[i],更新答案为中间位置ans = mid;// 将右指针移到中间位置左边，继续查找是否有更小满足条件的r = mid - 1;}else {// 如果中间元素不大于b[i],将左指针移到中间位置右边l = mid+1;}}// 累加满足元素之和ret += n-ans+1;}System.out.println(ret);}
}

5、未来竞赛

时间飞逝，转眼间来到了5025年，蓝桥杯大赛已经成为全球瞩目的盛事，吸引了来自世界各地的顶尖选手。每个国家和地区都派出了自己的精英队伍，准备在这场科技盛宴中大显身手。

本次大赛共有 N 位参赛者，第 i 位参赛者的编号位 i，来自编号为 A_i 的国家。比赛机房的电脑从左到右依次编号为 1 到 N，每位参赛者将在与自己编号相同的电脑上进行比赛。为了确保比赛的公平性，蓝桥杯官方决定对部分参赛者的电脑进行抽样监控。然而，监控方式必须满足以下条件：

1. 监控的电脑数量不能为零。
2. 同一个国家或地区的参赛者最多只能有两台电脑被监控，不能过多集中监控某个国家的选手。
3. 如果同一个国家或地区的两台电脑被监控，它们之间的距离不能超过 D。这里的距离定义为两台电脑编号之差的绝对值。

由于可能的监控方式实在太多，官方一时难以计算，于是他们向你求助，希望你能帮忙计算出所有合法的监控方式数量。

由于结果可能非常庞大，请将答案对 10⁹+7 取模后输出。

解题代码：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int MOD = 1000000007;int N = sc.nextInt();  // 表示参赛者数量int D = sc.nextInt();  // 表示选取的距离要求int[] arr = new int[N];// 参赛者编号for (int i = 0; i < N; i++) {arr[i] = sc.nextInt();}HashMap<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < N; i++) {int country = arr[i];int computer = i+1;map.computeIfAbsent(country, k -> new ArrayList<>()).add(computer);}long total = 1;for (List<Integer> list : map.values()) {Collections.sort(list);int C = list.size();long ways = 1; // 选0的方式数目ways += C; // 选1的方式数目long pairs = 0;int right = 0;for (int i = 0; i < list.size(); i++) {while (right < list.size() && list.get(right) - list.get(i) <= D) {right++;}pairs += (right - i - 1);}ways += pairs;total = (total * ways) % MOD;}total = (total - 1 + MOD) % MOD; // 防止负数System.out.println(total);}
}

6、备份比赛数据

蓝桥杯大赛的组委会最近遇到了一个棘手的问题。他们有 N 台电脑需要备份比赛数据，每台电脑所需的备份时间分别为 A1,A2,…,AN 分钟。

备份必须按编号顺序依次进行，即先第 1 台，再第 2 台，依此类推。每台电脑的备份需要工作人员持续操作，且必须安排在同一天内完成。例如，如果某台电脑的备份需要 5 分钟，那这 5 分钟必须安排在同一天，不能拆分到两天。如果当天剩余时间不足以完成某台电脑的备份，那就只能推迟到第二天进行。

每台电脑备份完成后，系统需要等待 Bi 分钟才能开始下一台的备份。这段等待时间不需要工作人员操作，且可以跨天进行。例如，如果第 1 台电脑的备份在第 1 天结束时完成，且 B1=10 分钟，那么第 2 台电脑的备份只需在第 2 天开始后等待 10 分钟就能进行。

现在，组委会希望尽量缩短每天的工作时间，以便工作人员能尽早下班休息。但上级有要求，所有电脑的备份必须在最多 T 天内完成。对此，请你帮助蓝桥杯组委会计算出每天最少需要安排的工作时间 M（M 最大不可超过 3600），以便所有电脑的备份能在 T 天内顺利完成。如果无论如何都无法满足条件，请直接输出 −1。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();   // 电脑数量int T = sc.nextInt();   // 最多允许的天数int[] A = new int[N];   // 每台电脑的备份时间int[] B = new int[N];   // 每台电脑备份后等待时间// 最大的单个备份时间int maxA = 0;for (int i = 0; i < N; i++) {A[i] = sc.nextInt();if (A[i] > maxA) {maxA = A[i];}}for (int i = 0; i < N; i++) {B[i] = sc.nextInt();}sc.close();// 每天工作时间 M 的下界为 maxA（至少能完成最耗时备份），上界为3600int left = maxA, right = 3600, ans = -1;while (left <= right) {int mid = (left + right) / 2;if (canFinish(mid, N, T, A, B)) {ans = mid;right = mid - 1;} else {left = mid + 1;}}System.out.println(ans);}// 模拟：以每天工作时间 M 是否能在 T 天内完成所有备份任务static boolean canFinish(int M, int N, int T, int[] A, int[] B) {int days = 1;int currentTime = 0;  // 当前天已占用的时间// 安排第一台电脑的备份currentTime = A[0];// 对后续每台电脑依次安排for (int i = 1; i < N; i++) {// 先安排等待时间（等待时间可以跨天）int waiting = B[i - 1];while (waiting > 0) {int remaining = M - currentTime;if (remaining >= waiting) {currentTime += waiting;waiting = 0;} else {waiting -= remaining;days++;currentTime = 0;if (days > T) return false;}}// 再安排备份 A[i]（必须在一天内连续完成）if (currentTime + A[i] <= M) {currentTime += A[i];} else {days++;currentTime = A[i];if (days > T) return false;}}return days <= T;}
}

有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~✨️✨️✨️