本文主要是介绍N长数列其子数列K倍区间二分不可解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
# [蓝桥杯 2017 省 B] k 倍区间
## 题目描述
给定一个长度为 $N$ 的数列，A[1],A[2],...A[N]，如果其中一段连续的子序列 A[i],A[i+1],...A[j](i <= j)之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K。
以下 N行每行包含一个整数 A[i]。
## 输出格式
输出一个整数，代表 $K$ 倍区间的数目。
## 样例 #1
### 样例输入 #1
```
5 2
1
2
3
4
5
```### 样例输出 #1
```
6
这个问题乍一看好像是《数据结构与算法分析 Java语言描述》里面刚开始的二分的例子——求数列的最大子数列和的变体，然而，实际上，这道题目根本不可能用二分法去解决。
package 练习; import java.util.*;public class K倍区间 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt();int K = scan.nextInt();scan.nextLine(); int[] A = new int[N]; for (int i = 0; i < N; i++) { A[i] = scan.nextInt(); scan.nextLine(); }/* for (int i = 0; i < N; i++) { int sum = 0; // 每次外层循环开始时，重置sum为0for (int j = i + 1; j < N; j++) { sum = sum + A[j]; if (sum % K == 0) {number++; } } }*/System.out.println( Karea(A , 0 , N - 1 , K) );} public static int Karea(int[] A , int left , int right , int K) {if(left == right) {if(A[left] % K == 0)return 1;elsereturn 0;}int center = ( left + right ) / 2;int leftKarea = Karea(A , left , center, K);int rightKarea = Karea(A , center + 1 , right , K);int leftBorderNumber = 0 , leftBorderSum = 0;for(int i = center ; i >= left ; i--){leftBorderSum += A[i];if(leftBorderSum % K == 0)leftBorderNumber ++;}int rightBorderNumber = 0 , rightBorderSum = 0;for(int i = center ; i <= right ; i++){rightBorderSum += A[i];if(rightBorderSum % K == 0)rightBorderNumber ++;}if(rightBorderSum % K ==0)rightKarea ++;return leftBorderNumber * rightBorderNumber + leftKarea + rightKarea;}}//到时候用二分法，这个因为是时间复杂度太大了
这是仿造书上的代码所写的，通过了题目所给的那个例子。
原来的没有加上
if(rightBorderSum % K ==0)rightKarea ++;是我忽略了
int rightKarea = Karea(A , center + 1 , right , K);这面的center + 1，这使得center位置的数不能和后面的数组合。
一个思路是修改代码。
int rightKarea = Karea(A , center , right , K);然而实际结果就是IDEA会不断报错。
我们不妨再次考虑这道题目给出的那个例子
5 2
1
2
3
4
5
我把它们换成行，以便表示(假设传的是center)
0 1 2 3 4 （这里的数组是下面数字对应的数组下标）
1 2 3 4 5
毫无疑问，a[0] == 1为第一个左，a[5] == 5为第2个右。而a[2] = 3是这两个数所确定的第一个center【1】，a[2] == 3。
继续下去3、4和5被当作数据继续向下调用，这个时候就足够发现问题的关键所在，而无须管另外一组数了。
这个层级的left是center【1】，a[2] == 3。right是4。就向下调用因为这一层的两个数确定的center【2】，也就是a[3] == 4被传到下一个调用层级的时候是center 【2】就是这一层的左判断也就是a[2] ==3，而右判断饭还是a[4] ==5 .
再往下center【2】，a[3] == 4就变成了左判断，right不变还是a[4] == 5。这两个数确定了center【3】，a[3] == 4。
再往下去center【3】就又变成了a[3] == 4（int （3 + 4）/ 2 == 3）就陷入了死循环
建议自己试一试
if(rightBorderSum % K ==0)rightKarea ++;但是不要依赖具体的例子
虽然center左边的 N * K + b（或者b + N * K） 右边的 M * K + c （或者c + M * K ）然而你不能保证b + c不等于K的倍数
如果，在二分的基础上再全搜索就超时了。
而且你传center到做左边，左边还是会把center放到可能里面，会重复。而这样的代码错误是不可避免的，所以二分对这个问题是完全无解的。
其实当有涉及到中心center的时候二分全查减低时间复杂度都只对“ 涉及到center” 而且不怕重复的，比如说求最大子序列和——因为max只需要判断有没有比自己大的而不用管有没有重复，只要全部情况都遍历到了就行，几种情况多出来是没有什么很大的影响的。
这篇关于N长数列其子数列K倍区间二分不可解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
