电子产品商务网站模板,上海的广告公司有哪些,网站备案成功怎么查备案号,成都服务器idc托管题目大意
平面上有n个点#xff0c;给出m个询问#xff0c;每个询问要回答从x轮流往右往左去到最远的点#xff0c;最后到达的点 解题思路
对于每个询问#xff0c;每次二分左右可以到多远#xff0c;直到不能动为止
考虑时间#xff0c;对于重复走一个范围的#xf…题目大意
平面上有n个点给出m个询问每个询问要回答从x轮流往右往左去到最远的点最后到达的点 解题思路
对于每个询问每次二分左右可以到多远直到不能动为止
考虑时间对于重复走一个范围的可以直接模掉
对于范围缩小的如下图如果走了黑的的一段则下一段的长度不会大于红色的一段上面是因为如果大于则可以走完一程下面的是因为范围最大为红色所以每一次走的距离会小于上一次的一半
所以时间复杂度为O(mlognlog109)O(m\ logn\ log10^9)O(m logn log109)
code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 200021
#define mp make_pair
#define fs first
#define sn second
using namespace std;
ll n,m,x,k,l,r,L,R,mid,len,v[N],a[N];
pairll,llb[N];
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%lld,x);b[i]mp(x,i);}sort(b1,b1n);for(ll i1;in;i)v[b[i].sn]i,a[i]b[i].fs;len(a[n]-a[1])*2;if(n1){while(m--)puts(1);return 0;}while(m--){scanf(%lld%lld,x,k);xv[x];k%len;lx;rn;while(lr){//先走到最后面midlr11;if(ka[mid]-a[x])rmid-1;else lmid;}L1;Rl;k-a[l]-a[x];while(LR){k%(a[R]-a[L])*2;lL;rR;while(lr){//来回走midlr1;if(ka[R]-a[mid])lmid1;else rmid;}Ll;k-a[R]-a[l];lL;rR;while(lr){midlr11;if(ka[mid]-a[L])rmid-1;else lmid;}Rl;k-a[l]-a[L];}printf(%lld\n,b[L].sn);}return 0;
}
