题意简化:将书本进行排序后,假设每本书阅读时间对应不同区间,现在给出每本书对应的区间长度。假如阅读者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;
}
}
}
}