题意略.
思路:
我们可以把 bi[i] 在 ai[ ] 中的位置记录下来, 然后算出 i - mp[ bi[i] ] , 再将它压入一个 multiset. 每次我们就二分地来寻找离 0 最近的数字来作为答案.
那当我们循环左移的时候怎么办呢? 把每个数字都减一, 把当前 bi[i] 产生的数字重新赋值再压入吗?
当然不是, 我们可以改变 0 参考系, 也即二分地来寻找离 i 最近的数字来作为答案.(i 从 0 开始, 因为第一个答案相当于循环左移 0 次)
那么要删去的那个数字怎么办呢?
我们将它删去后, 压入的值是 (i + n) - mp[ bi[i] ]. 可是为什么呢?
可以认为是 参考系的值 + n - mp[ bi[i] ] (原本应该改成的值).
也可以认为是, 当前在 multiset 中的值其实都已经减去了 i , 为了补上这个 i, 我要在 n - mp[ bi[i] ] 上加上 i.
详见代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 5;
- int mp[maxn],bi[maxn],n;
- multiset<int> st;
- int main(){
- int n;
- scanf("%d",&n);
- int temp;
- for(int i = 0;i <n;++i){
- scanf("%d",&temp);
- mp[temp] = i;
- }
- for(int i = 0;i < n;++i){
- scanf("%d",&bi[i]);
- st.insert(i - mp[bi[i]]);
- }
- for(int i = 0;i < n;++i){
- multiset<int>::iterator it = st.lower_bound(i);
- int ans = maxn;
- if(it != st.end()) ans = min(ans,(*it) - i);
- if(it != st.begin()) ans = min(ans,i - *(--it));
- printf("%d\n",ans);
- int t = i - mp[bi[i]];
- st.erase(st.find(t));
- st.insert((i + n) - mp[bi[i]]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2713636.html