【题解】二分 | [USACO 2009 Dec S]Music Notes

题目链接：[USACO 2009 Dec S]Music Notes

本地运行没问题但是提交到平台先是显示段错误，于是修改了mid的部分，二分修改左边界是有当 $l=r-1$ 的时候可能会死循环的问题，但是修改之后仍然显示运行超时，这是运行超时的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef long long ll;

const int maxn = 10010;
int N, Q;
ll B[maxn];

//[0, B1) plays note 1, [B1, B2) plays note 2...

int main()
{
	scanf("%d %d", &N, &Q);
	B[0] = 0;
	scanf("%lld", &B[1]);
	for (int i = 2; i <= N; i++)
	{
		scanf("%lld", &B[i]);
		B[i] += B[i - 1];
	}
	for (int i = 0; i < Q; i++)
	{
		ll q;
		scanf("%lld", &q);
		int l = 0, r = N;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			printf("mid = %d\n", mid);
			if (B[mid] <= q)  l = mid + 1;
			else r = mid;
		}
		printf("%d\n", l);
	}
	return 0;
}

从头仔细看了一次后发现最多有50000个notes，因此设成10010显然不够，多加了一个零，但仍然超时，尝试去掉在 $mid$ 更新的时候加的1之后程序通过了，通过的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef long long ll;

const int maxn = 100010;
int N, Q;
ll B[maxn];

//[0, B1) plays note 1, [B1, B2) plays note 2...

int main()
{
	scanf("%d %d", &N, &Q);
	B[0] = 0;
	scanf("%lld", &B[1]);
	for (int i = 2; i <= N; i++)
	{
		scanf("%lld", &B[i]);
		B[i] += B[i - 1];
	}
	for (int i = 0; i < Q; i++)
	{
		ll q;
		scanf("%lld", &q);
		int l = 0, r = N;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (B[mid] <= q)  l = mid + 1;
			else r = mid;
		}
		printf("%d\n", l);
	}
	return 0;
}

所以还是没理解明白更新区间端点的问题。

二分思路梳理：按照某种性质将区间分成两部分，一部分满足，一部分不满足，二分的目标是找出这个分界（左区间的右端点或右区间的左端点）。

二分的步骤（以本题目为例）：

1. 确定左右端点，取中点；

2. 判断中点是否是否满足性质并更新区间。这里 $if$ 语句的条件是当 $mid$ 对应的下标的值不晚于查询的时间时为不满足的情况，此时mid不满足，那么对于有序区间比较大小来说，左侧区间的一切都不满足，而端点是整数，因此更新左端点为 $mid+1$ ,题目要找的 $notes$ 实质上是找比所查询的时间大的 $notes$ 里最小的那一个（因为 $notes$ 的计算方式是一个左闭右开区间，时刻从 $0$ 开始计时，给出的 $B_i$ 是持续时间），因此当当前中点对应的下标索引出的值大于查询时间时，就有可能是最终答案，因此更新右端点就为中值即可；

3. 输出，此处循环终止的条件是左端点小于右端点，而实际上终止时并不会出现 $r<l$ 的情况，这是因为在初始化时右端点是严格大于左端点的，随后C++的除法是下取整的机制，唯一可能出现问题的是 $l=r-1$ 的情况，本题目中相当于是用查询时刻将整个曲子区间分成两段，左区间是已经演奏结束的部分，右区间是没有演奏的部分，因此就是找右区间左端点的值。出现上述极端情况时由于除法下取整机制，$mid$ 初始化为 $l$，如果满足 $if$ 语句的条件，那么左端点会等于右端点，随后循环终止，如果不满足，那么右端点会等于左端点，循环也会正常终止。

p.s.一开始修改代码 $mid=l+r+1>>1$ 的操作会出现问题的情况是把 $mid$ 划分到右端点区间，并且判断语句中满足条件更新左端点为 $mid$ 时才会出现的，这样当左右端点只相差1又恰好满足条件时，$mid$ 将始终得不到更新，就会出现死循环；而我在更新时由于 $if$ 条件实际上是不满足需求的情况（要找的是严格大于当前时刻的最小下标值），因此更新时如果再加上1，$mid=r-1+r+1>>1=r$当执行 $else$ 语句时就会出现 $ r = mid = r$ 的情况，就会出现死循环。当选择找左区间右端点最大值时往往会设置

if(check(mid))  l = mid;
else  r = mid - 1;

这种情况下的 $mid$ 更新时需要加1防止死循环发生：

mid = l + r + 1 >> 1;

这是因为：

l = r - 1;
mid = r - 1 + r >> 1 = r - 1 = l 下取整导致得不到更新
check(mid) = true 时，l = mid = l  继续循环

所以实际上需要判断的是由于除法下取整可能会导致的边界得不到更新的问题。