《从入门到精通：蓝桥杯编程大赛知识点全攻略》（六）-分巧克力、K倍区间

前言

在本博客中，我们将讨论两种常见的算法技巧——二分法和前缀和，并通过实际问题来进行应用。首先，我们会通过二分法解决一个经典的“巧克力分配问题”，该问题需要我们在不同的分配方案中找到最优的解。接着，我们将使用前缀和来解决一个关于区间问题的挑战——计算给定区间内能够被 k 整除的子数组的数量。这两个问题通过不同的算法技巧为我们提供了高效求解复杂问题的思路。接下来，进入具体的解决方案和代码实现。

分巧克力

儿童节那天有 K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力，其中第 i块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N块巧克力中切出 K块巧克力分给小朋友们。
切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块 6×5的巧克力可以切出 6块 2×2的巧克力或者 2块 3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi和 Wi。
输入保证每位小朋友至少能获得一块 1×1的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤100000
,1≤Hi,Wi≤100000
输入样例：

java">2 10
6 5
5 6

输出样例

java">2

算法思路

在这里插入图片描述
根据上述图示，我们可以很清楚的得到一个规律，切的正方形的巧克力的边长越长，块数越少。并且得到的巧克力的块数是大巧克力的长 / 正方形巧克力的边长 * 大巧克力的宽 / 正方形巧克力的边长（例如样例 6 / 2 * 5 / 2 = 6）；此时就可以通过二分来进行处理，找到块数大于k且正方形巧克力的边长最大值。
用整型变量n记录大巧克力的块数，k记录最小需要多少块巧克力，整型数组h用来记录大巧克力的长，整型数组w来记录大巧克力的宽；题目保证每位小朋友至少能获得一块 1×1的巧克力，所以答案最小值是1，最大值就是大巧克力的最大边长100000；故左边界left = 1，right = 100000。
进行二分查找，判断条件做一个函数check，传递的参数是要切的巧克力的边长mid，整型变量res来记录最后切的巧克力的块数。然后遍历每个大巧克力即（res += (h[i] / mid) * (w[i] / mid)），当res >= k时说明条件成立返回true，小于k时返回fasle。
此时判断条件函数已经写好，当切好的巧克力的块数大于k时，又因为我们需要边长尽可能大，所以块数应该减少，故左区间右移即left = mid；当切好的巧克力的块数小于k时，说明切巧克力的边长应该减少让块数向k接近，故右区间左移即right = mid - 1。最后的答案left就是我们最后需要的巧克力块数最少是k且边长的最大值。

上述二分存在一种情况，当区间长度只有2个元素时即L = R -1，中点mid = （L + R）/ 2 = L，但是答案在右区间故需要左区间右移，但tttL = mid= L形成死循环，故mid = （L + R + 1）/ 2 可以避免这种情况。

代码如下

java">
import java.io.*;
public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int n,k;//长度static int[] h = new int[N];//宽度static int[] w = new int[N];public static void main(String[] args)throws Exception {n = nextInt();k = nextInt();for(int i = 0;i < n;i++){h[i] = nextInt();w[i] = nextInt();}int left = 1;int right = 100000;while(left < right){int mid = (left + right + 1)/2;if(check(mid)){left = mid;}else {right = mid - 1;}}pw.println(left);pw.flush();}public static boolean check(int mid){int res = 0;for(int i = 0;i < n;i++){res += (h[i] / mid) * (w[i] / mid);if(res >= k){return true;}}return false;}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}

前缀和知识点可以看我的这两篇博客（一维数组的前缀和、二维数组的前缀和和子矩阵的和）

K倍区间

给定一个长度为 N的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj
之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数，代表 K倍区间的数目。
数据范围
1≤N,K≤100000,1≤Ai≤100000
输入样例

java">5 2
1
2
3
4
5

输出样例

java">6

算法思路

在这里插入图片描述

这道题的暴力做法（会超时）：
枚举每一个终点right从1到n，然后枚举每一个起点left从1到right，再用前缀和数组求区间和，最后%k求余数是否为0。
接下来进行优化：
在R固定的时候，有多少个L满足(s[R] - s[L - 1]) % k == 0是内层循环的含义。可以转化为当R固定时，在0 ~ R - 1之间找到有多少个L满足(s[R] - s[L]) % k == 0可转换为：s[R] % k == s[L] % k即有多少个S[L]与S[R]对k的余数相同。
定义一个整型数组cnt，cnt[i]表示余数为i的数有多少个。
res 用于统计满足条件的子数组数量。
cnt[0] = 1 初始化，因为 s[0] % k == 0 是合法的，表示从数组的开头到某个位置的和能被 k 整除。
for 循环枚举每个可能的右边界 R，根据当前的前缀和 s[R] % k 来判断是否有子数组和能被 k 整除。
如果 cnt[s[R] % k] 大于 0，说明之前有某些前缀和余数与当前前缀和余数相同，从而形成了一个符合条件的子数组。
每次发现符合条件的子数组后，更新 cnt[s[R] % k]。

代码如下

暴力做法（会超时）

java">import java.util.Scanner;public class Main {static int N = 100010;static int[] a = new int[N]; // 原数组static int[] s = new int[N]; // 前缀和数组public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();s[i] = s[i - 1] + a[i]; // 公式一}int res = 0;for (int right = 1; right <= n; right++) { // 右端点for (int left = 1; left <= right; left++) { // 左端点 int sum = s[right] - s[left - 1]; // 公式二if (sum % k == 0) res++;}}System.out.print(res);}
}

最终优化版本

java">import java.io.*;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int[] cnt = new int[N];//前缀和数组static long[] s = new long[N];public static void main(String[] args)throws Exception {int n = nextInt();int k = nextInt();for(int i = 1;i <= n;i++){s[i] = s[i-1] + nextInt();}long res = 0;//cnt[0] = 1 初始化，因为 s[0] % k == 0 是合法的，表示从数组的开头到某个位置的和能被 k 整除。cnt[0] = 1;for(int right = 1;right <= n;right++){//如果 cnt[s[right] % k] 大于 0，说明之前有某些前缀和余数与当前前缀和余数相同，从而形成了一个符合条件的子数组。res += cnt[(int)(s[right] % k)];cnt[(int)(s[right] % k)]++;}pw.println(res);pw.flush();}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}