題目大意

平面上有n個點，給出m個詢問，每個詢問要回答從x輪流往右往左去到最遠(yuǎn)的點，最后到達(dá)的點

---

解題思路

對于每個詢問，每次二分左右可以到多遠(yuǎn)，直到不能動為止

考慮時間，對于重復(fù)走一個范圍的，可以直接模掉

對于范圍縮小的（如下圖），如果走了黑的的一段，則下一段的長度不會大于紅色的一段（上面是因為如果大于則可以走完一程，下面的是因為范圍最大為紅色），所以每一次走的距離會小于上一次的一半

所以時間復(fù)雜度為$O(mlognlog10^9)$

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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]; pair<ll,ll>b[N]; int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;++i){scanf("%lld",&x);b[i]=mp(x,i);}sort(b+1,b+1+n);for(ll i=1;i<=n;++i)v[b[i].sn]=i,a[i]=b[i].fs;len=(a[n]-a[1])*2;if(n==1){while(m--)puts("1");return 0;}while(m--){scanf("%lld%lld",&x,&k);x=v[x];k%=len;l=x;r=n;while(l<r){//先走到最后面mid=l+r+1>>1;if(k<a[mid]-a[x])r=mid-1;else l=mid;}L=1;R=l;k-=a[l]-a[x];while(L<R){k%=(a[R]-a[L])*2;l=L;r=R;while(l<r){//來回走mid=l+r>>1;if(k<a[R]-a[mid])l=mid+1;else r=mid;}L=l;k-=a[R]-a[l];l=L;r=R;while(l<r){mid=l+r+1>>1;if(k<a[mid]-a[L])r=mid-1;else l=mid;}R=l;k-=a[l]-a[L];}printf("%lld\n",b[L].sn);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【二分】走亲戚的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。