RT 题解代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+40;
int f[MAXN],n,ans=1e9,siz[MAXN],top,q[MAXN];
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&f[i]);
	sort(f+1,f+n+1);
	for(int i=1;i<=n;i++){
		int pos=lower_bound(q+1,q+top+1,f[i])-q; //查找当前成员应该放在那一组 
		while(q[pos+1]==f[i]&&pos<top) pos++; //一直找到相等的最后一个 
		if(pos>top||q[pos]!=f[i]) siz[++top]=1,q[top]=f[i]+1; //无法更新，重开一个组 
		else siz[pos]++,q[pos]++; //对当前组更新 
	}
	for(int i=1;i<=top;i++) ans=min(ans,siz[i]); //对所有组取最小值 
	printf("%d\n",ans);
	return 0;
}

将第12行的

int pos=lower_bound(q+1,q+top+1,f[i])-q;

改为

int pos=lower_bound(q+1,q+n+1,f[i])-q;

后，答案出错，在该语句后添加调试代码：

cout<<q[2]<<' '<<f[i]<<' '<<pos<<endl;

输入：

7
4 5 2 3 -4 -3 -5

原代码输出结果为：

当 $i=5$ 或 $i=6$ 时，$pos=n+1=8$ 说明 $lower\_bound()$ 没有找到一个大于等于 $f[i]$ 的 $q[]$,但是 $q[2]=3>f[6]>f[5]$ 为什么会找不到呢？