題解 - 回到过去 - 南阳理工学院OJ (nyist.edu.cn) 这是上次的题解，这次的题与上次的题思路大概一致，只不过数据中多了 $0$ 这个数据

在上次的二分中，我们是枚举 $i$ 来找到第一个满足的 $r$ 然后答案 $+= (n - l + 1)$ 代码如下 $：$

#include<stdio.h>

long long int a[100005], sum[100005];
int main()
{    
    int n, k;
    
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
	}
	
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	
	long long cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		int l = 1, r = n, mid;
		while(l < r)
		{
			mid = (l + r) / 2;
			if(sum[mid] >= sum[i - 1] + k) r = mid;
			else l = mid + 1;
		}

		if(sum[l] - sum[i - 1] >= k) cnt += (n - l + 1);
		
	}
	
	printf("%lld",cnt);
	return 0;
}

这是上次题解中二分的码，我们的二分边界为 $l = 1 , r = n$ 由于上次的数据中没有数据零，所有我们最后二分查找的结果 $l$ 也就是第一个满足的下标 是一定大于等于 $i$ 的，所以并不会出现错误。 但如果出现数据零，我们的二分边界要改成 $l = i , r = n$ 不然我们所查找的下标可能会比 $i$ 小从而使最终答案比标准答案变多。

例如 此时有这个题目 $:$ 我们有 $a$ 数组，里面有 $n$ 个数，我们想要找到大于等于 $a_i + x$ 且大于等于 $i$ 的第一个下标 $(a 数组是序的)$

第一行输入 $n$ $x$ 第二行为 $a_1 , a_2 .... a_n$

5 0
1 3 7 7 9

1 2 3 4 5

for(int i = 1; i <= n; i++)
	{
		int l = 1, r = n, mid;
		
		while(l < r)
		{
			mid = (l + r) / 2;
			if(a[mid] >= a[i] + x) r = mid;
			else l = mid + 1;
		}
		
		cout << l << '\n';
	}

但这个二分查找的结果却为 $1$ $2$ $3$ $3$ $5$

这是因为如果我们的二分边界 $l$ 依然从$1$ 开始 $,$ 那当 $i = 4$ 时，由于我们的二分查找找的是大于等于 $a_i + x = 7$ 的第一个下标 $,$所以我们会找到第一个 $7$ 的下标也就是 $3$ 但我们需要的答案应该时大于等于 $i = 4$ 的 $,$ 所以会错 $.$ 所以我们只需要改一下二分的边界 $l$ 就可以避免这个错误 $,$ 因为我们需要找到大于等于 $i$ 的某个下标 $,$ 所以我们只需要这么改 $:$

for(int i = 1; i <= n; i++)
	{
		int l = i, r = n, mid;
		
		while(l < r)
		{
			mid = (l + r) / 2;
			if(a[mid] >= a[i] + x) r = mid;
			else l = mid + 1;
		}
		
		cout << l << '\n';
	}

也就是把 $l = 1$ 改为 $l = i$ 这就避免了所找的下标小于 $i$ 这个问题

ps : 因为想到再次出这个题 并且加上 0 这个数据， 所以在上次的题解中故意将二分边界 改为$l = 1$ 而不是 $l = i$ 以及在上次的双指针代码中也卡掉了 0 这个数据， 大家可以想想如何对双指针的代码进行修改，从而避免这个数据的错误

有任何问题可以在评论区问