感觉除了两个点在那循环的部分, 其他时候绳子的长度每次变为一半一下, 就变成了Log(l)步。。
然后就暴力找就好啦, 循环的部分取个模。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 2e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); int n, m, a[N], x[N], id[N]; bool cmp(const int& a, const int& b) { return x[a] < x[b]; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); x[i] = a[i]; id[i] = i; } sort(id + 1, id + 1 + n, cmp); sort(x + 1, x + 1 + n); while(m--) { int p, l; scanf("%d%d", &p, &l); while(1) { int be = p, len = 0; int it1 = upper_bound(x + 1, x + 1 + n, a[p] + l) - x - 1; len += abs(x[it1] - a[p]); l -= abs(x[it1] - a[p]); p = id[it1]; int it2 = lower_bound(x + 1, x + 1 + n, a[p] - l) - x; len += abs(x[it2] - a[p]); l -= abs(x[it2] - a[p]); p = id[it2]; int ed = p; if(be == ed && be == id[it1]) { break; } if(be == ed) { l %= len; } } printf("%d ", p); } return 0; } /* */