训练营D9T2:爱看书的思考者

发布时间 2023-10-26 13:31:46作者: Final_Kopicy

题意简化:将书本进行排序后,假设每本书阅读时间对应不同区间,现在给出每本书对应的区间长度。假如阅读者0时刻开始阅读,输入当前时间,输出当前时间对应阅读的书本。

 

十分典型的二分查找。就是找到一个区间使得当前时间恰好卡在书本位置。

为此可以将每一本书对应的左右区间求出,用二分查找的方法找到当前对应的书本。

int kkk=0;
	for(int i=1;i<=n;i++){
		L[i]=kkk;R[i]=kkk+bb[i].t-1;
		kkk+=bb[i].t;
	}//L[]是书本阅读时间左区间,R[]是书本阅读时间右区间
	int q;
	cin>>q;
	while(q--){
		int w;
		cin>>w;
		if(w>=kkk) {
			cout<<"naNa"<<endl;
			continue;
		}
        //二分查找
		int mid,l=1,r=n;
		while(l<=r){
			mid=l+r>>1;
			if(R[mid]<w) l=mid+1;
			else if(L[mid]>w) r=mid-1;
			else if(L[mid]<=w&&R[mid]>=w){
				cout<<bb[mid].k<<endl;//找到,中止二分。
				break;
			}
		}
	}
}